### Ranking tournaments: Local search and a new algorithmRanking tournaments: Local search and a new algorithm

Access Restriction
Subscribed

 Author Coleman, Tom ♦ Wirth, Anthony Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Local search ♦ Approximation ♦ Feedback arc set Abstract Ranking is a fundamental activity for organizing and, later, understanding data. Advice of the form $“\textit{a}$ should be ranked before $\textit{b}”$ is given. If this advice is consistent, and complete, then there is a total ordering on the data and the ranking problem is essentially a sorting problem. If the advice is consistent, but incomplete, then the problem becomes topological sorting. If the advice is inconsistent, then we have the feedback arc set (FAS) problem: The aim is then to rank a set of items to satisfy as much of the advice as possible. An instance in which there is advice about every pair of items is known as a tournament. This ranking task is equivalent to ordering the nodes of a given directed graph from left to right, while minimizing the number of arcs pointing left. In the past, much work focused on finding good, effective heuristics for solving the problem. Recently, a proof of the NP-completeness of the problem (even when restricted to tournaments) has accompanied new algorithms with approximation guarantees, culminating in the development of a PTAS (polynomial time approximation scheme) for solving FAS on tournaments. In this article, we reexamine many existing algorithms and develop some new techniques for solving FAS. The algorithms are tested on both synthetic and nonsynthetic datasets. We find that, in practice, local-search algorithms are very powerful, even though we prove that they do not have approximation guarantees. Our new algorithm is based on reversing arcs whose nodes have large indegree differences, eventually leading to a total ordering. Combining this with a powerful local-search technique yields an algorithm that is as strong, or stronger than, existing techniques on a variety of data sets. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2010-01-05 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 14 Page Count 17 Starting Page 2.6 Ending Page 2.22

#### Open content in new tab

Source: ACM Digital Library