Aggregating Inconsistent Information: Ranking and Clustering

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Aggregating Inconsistent Information: Ranking and Clustering
Speaker:Nir Ailon
Affiliation:Princeton University and Member, School of Mathematics
Date:Tuesday, April 10
Time/Room:10:30am - 12:30pm/S-101

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.