Proofs of Conjectures in "Aggregating Inconsistent Information: Ranking and Clustering"
Report ID: TR-719-05Author: Newman, Alantha / Ailon, Nir / Charikar, Moses
Date: 2005-01-00
Pages: 16
Download Formats: |PDF|
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.