Abstract:

In this talk, I will address optimization problems in which we are 
given
contradictory pieces of input information and the goal is to find a
globally consistent solution that minimizes the number of
disagreements with the respective inputs.  Specifically, the problems
I will address are rank aggregation and consensus clustering.
In rank aggregation we are given a set of rankings (permutations) on
some ground set and we wish to find one ranking that minimizes the
total number of pairwise disagreements with the input rankings
(a natural distance measure between permutations).
In consensus clustering we are given a set of clusterings of some
ground set and we wish to find one clustering that minimizes the
total number of pairwise disagreements with the input clusterings.

The two problems are closely related to two well known optimization
problems on complete graphs, which are interesting in their own
right: The minimum feedback arc set in tournaments problem and
the correlation clustering problem.  I will describe the relation
between these problems, and will present simple combinatorial 
algorithms
that guarantee improved approximation algorithm for both unweighted 
and
weighted versions.  This will lead to a 1.57 approximation factor for
both rank aggregation and consensus clustering, improving on the 
previous
best factor of 2.

A variant of the combinatorial algorithm can be used to round
certain LP relaxations of the above problems.  This method further
pushes the approximation factor from 1.57 down to 4/3.

All the problems I will address were previously known to be
NP-hard except for the feedback arc set problem on tournaments,
which was conjectured to be NP-hard.  If time permits, I will
describe a new (randomized) reduction showing that this problem
is NP-hard as well.

This is joint work with Moses Charkiar and Alantha Newman.