How to rank with fewer errors: A PTAS for feedback arc set in tournaments
Warren Schudy (Brown University)
April 22, 2009
Suppose you ran a chess tournament, everybody played everybody, and you wanted to use the results to rank everybody. Unless you were really lucky, the results would not be acyclic, so you could not just sort the players by who beat whom. A natural objective is to find a ranking that minimizes the number of upsets, where an upset is a pair of players where the player ranked lower in the ranking beat the player ranked higher. This is the minimum feedback arc set (FAS) problem in tournaments. We present the first polynomial time approximation scheme (PTAS) for this problem. A weighted generalization gives the first PTAS for Kemeny rank aggregation. The runtime is singly exponential in $1/\epsilon$, improving on the conference version of this work, which was doubly exponential.

Joint work with Claire Mathieu.