Computer Science/Discrete Mathematics Seminar I

A ranking of n web pages is to be chosen from outputs of k search engines. How do we choose one ranking minimizing the "disagreement" with the k rankings? A clustering of n genes is to be chosen from outputs of k clustering algorithms. How do we choose one clustering minimizing the "disagreement" with the k clusterings? These information aggregation problems date back to 1785, when the French philosopher Condorcet considered voting systems where each voter chooses a full ranking of a set of candidates. Recently, their algorithmic and complexity aspects have been studied. In this talk, I will describe new algorithms improving on the best known approximation ratios for both the ranking and the clustering problems with respect to a standard measure of disagreement. I will also discuss related graph theoretic optimization problems, known as the minimum feedback arc set in tournaments and the correlation clustering in complete graphs. Additionally, I will show that the problem of finding a minimum feedback arc set in tournaments has no poly-time algorithm, assuming NP is not contained in BPP. This almost settles a long-standing conjecture of Bang-Jensen and Thomassen, that the problem is NP-hard. This is joint work with Moses Charikar and Alantha Newman.