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.