Journal
JOURNAL OF THE ACM
Volume 55, Issue 5, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1411509.1411513
Keywords
Algorithms; Theory; Rank aggregation; consensus clustering; correlation clustering; minimum feedback arc-set; tournaments
Categories
Funding
- Princeton University
- National Science Foundation (NSF) ITR [CCR-0205594]
- DOE Early Career Principal Investigator award [FG02-02ER25540]
- NSF CAREER [CCR-0237113]
Ask authors/readers for more resources
We 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 extent of disagreement with the respective inputs. Specifically, the problems we address are rank aggregation, the feedback arc set problem on tournaments, and correlation and consensus clustering. We show that for all these problems (and various weighted versions of them), we can obtain improved approximation factors using essentially the same remarkably simple algorithm. Additionally, we almost settle a long-standing conjecture of Bang-Jensen and Thomassen and show that unless NP subset of BPP, there is no polynomial time algorithm for the problem of minimum feedback arc set in tournaments.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available