Ranking Tournaments: Local Search and a New Algorithm

Abstract

Ranking data is a fundamental organizational activity. Given advice, we may wish to rank a set of items to satisfy as much of that advice as possible. In the Feedback Arc Set (FAS) problem, advice takes the form of pairwise ordering statements, 'a should be ranked before b'. Instances in which there is advice about every pair of items is known as a tournament. This task is equivalent to ordering the nodes of a given directed graph to minimize the number of arcs pointing in one direction. 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..