IME: 1:30-2:20 pm,  October 16, 2007

PLACE: CSE 503  (NOTE CHANGE OF VENUE)

SPEAKER: Claire Mathieu
        Brown University and Microsoft Research

TITLE:  How to Rank with Few Errors


ABSTRACT:
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 on the
ranking beats the player ranked higher. This is the NP-hard minimum feedback arc
set (FAS) problem on tournaments. Our main result is a polynomial time
approximation scheme (PTAS) for this problem. A simple weighted generalization
gives a PTAS for Kemeny-Young rank aggregation.

Joint work with Warren Schudy.