Access Restriction

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

   Open content in new tab
Source: ACM Digital Library