MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Aggregating Inconsistent Information: Ranking and Clustering

Alantha Newman
RWTH-Aachen
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5  
AG Audience
English

Date, Time and Location

Thursday, 16 June 2005
13:30
45 Minutes
46.1 - MPII
024
Saarbrücken

Abstract

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 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.

Contact

Khaled Elbassioni
--email hidden
passcode not visible
logged in users only

Khaled Elbassioni, 06/08/2005 12:00 -- Created document.