|COMPUTER SCIENCE/DISCRETE MATH II|
|Topic:||Aggregating Inconsistent Information: Ranking and Clustering|
|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.