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 philosophers Condorcet and Borda considered voting systems in
which each voter specifies a full ranking of a set of candidates.
Recently, their algorithmic and complexity aspects have been studied.
We obtain improved algorithms for both these problems using a
remarkably simple principle. Our techniques also apply to related
graph optimization problems such as the minimum feedback arc set
problem on tournaments and the correlation clustering problem on
complete graphs. Additionally, we show that the problem of finding a
minimum feedback arc set on tournaments has no polynomial 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 Nir Ailon and Moses Charikar.