### DIMACS Theoretical Computer Science Seminar

Title: Aggregating Inconsistent Information: Ranking and Clustering

Speaker: **Moses Charikar**, Princeton University

Date: February 22, 2005 2:00-3:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

In this talk, I will address optimization problems that arise
in the context of aggregating inconsistent pieces of information.
The goal is to find a globally consistent solution that minimizes
the number of disagreements with the given inputs. I will discuss
such aggregation problems in the realm of ranking (rank aggregation)
and clustering (consensus clustering - also referred to as ensemble
clustering).

These aggregation problems are closely related to the well studied
optimization problem of minimum feedback arc set and the (relatively
newly studied) problem of correlation clustering. I will show
that for all these four problems, we can obtain improved approximation
factors using essentially the same, remarkably simple, combinatorial
algorithm.

All the problems I address were previously known to be
NP-hard except for the feedback arc set problem on tournaments.
We resolve the conjectured hardness of this problem by
showing NP-hardness (under randomized reductions).

This is joint work with Nir Ailon and Alantha Newman
(to appear in STOC 05).