How to rank with few errors

We present a polynomial time approximation scheme (PTAS) for the minimum feedback arc set problem on tournaments. A simple weighted generalization gives a PTAS for Kemeny-Young rank aggregation.

Authors

• Claire Mathieu
• Warren Schudy

Keywords

• Kemeny-Young rank aggregation
• approximation algorithm
• feedback arc set
• max acyclic subgraph
• polynomial-time approximation scheme
• tournament graphs