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.

Joint work with Claire Mathieu.