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