Proofs of Conjectures in "Aggregating Inconsistent Information: Ranking and Clustering"

Abstract:

In [ACN] ("Aggregating Inconsistent Information: Ranking and
Clustering", Manuscript, 2004), Ailon, Charikar and Newman address the problems
of rank aggregation, minimum feedback arc set in tournaments,
correlation clustering and consensus clustering. They present
new and improved combinatorial algorithms for approximating
these problems. They also present variants of these algorithms
based on linear programming rounding techniques, further improving
the approximation factors. The LP based results in [ACN] are,
however, left as conjectures based on numerical evidence. In
this work, which should be read as an annex to [ACN], we prove
these conjectures and henceforth establish theorems.