Computer Science/Discrete Mathematics Seminar II

In the past 2 years there has been considerable progress in the algorithmic problem of combining rankings (permutations on a ground set of "candidates") into a consensus ranking. This problem dates back to the 18th century, when the French philosopher Condorcet considered voting systems in which each voter specifies a full ranking of the candidates. Various versions of this problems appear in more recent surprising applications unrelated to voting. I will present my work with Moses Charikar and Alantha Newman on surprisingly simple approximation algorithms for a version of this problem with provably good constant approximation factors. En route, I will present the first known constant approximation algorithm for the related graph theoretic problem of minimum feedback arcset in tournaments. I will then survey some important results that followed our work, including Kenyon et al's more recent PTAS (presented earlier this year at the IAS). If time permits, I will discuss application of our techniques to some clustering problems. This is joint work with Moses Charikar and Alantha Newman.