Aggregating inconsistent information
Top Cited Papers
- 1 October 2008
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 55 (5), 1-27
- https://doi.org/10.1145/1411509.1411513
Abstract
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⊆BPP, there is no polynomial time algorithm for the problem of minimum feedback arc set in tournaments.Keywords
Funding Information
- National Science Foundation (CCR-0205594, CCR-0237113)
- U.S. Department of Energy (DE-FG02-02ER25540)
This publication has 19 references indexed in Scilit:
- Aggregation of Partial Rankings, p-Ratings and Top-m ListsAlgorithmica, 2008
- Ranking TournamentsSIAM Journal on Discrete Mathematics, 2006
- Fitting tree metrics: Hierarchical clustering and PhylogenyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Aggregating inconsistent informationPublished by Association for Computing Machinery (ACM) ,2005
- Correlation ClusteringMachine Learning, 2004
- The importance of being biasedPublished by Association for Computing Machinery (ACM) ,2002
- An Approximation Algorithm for Feedback Vertex Sets in TournamentsSIAM Journal on Computing, 2001
- A Polynomial Algorithm for the 2-Path Problem for Semicomplete DigraphsSIAM Journal on Discrete Mathematics, 1992
- Voting schemes for which it can be difficult to tell who won the electionSocial Choice and Welfare, 1989
- Spearman's Footrule as a Measure of DisarrayJournal of the Royal Statistical Society Series B: Statistical Methodology, 1977