Aggregating inconsistent information: ranking and clustering

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 number of disagreements 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.

REFERENCES

• 1: N. Ailon, M. Charikar, and A. Newman. Proofs of conjectures in 'aggregating inconsistent information: Ranking and clustering'. Technical Report TR-719-05, Princeton University, 2005.
• 2: N. Alon. Ranking tournaments (draft). Personal communication, 2004.
• 3: N. Alon and J. H. Spencer. The Probabilistic Method. Wiley, New York, 1992.
• 4: A. Frieze, A new rounding procedure for the assignment problem with applications to dense graph arrangement problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.21, October 14-16, 1996
• 5: Jørgen Bang-Jensen , Carsten Thomassen, A polynomial algorithm for the 2-path problem for semicomplete digraphs, SIAM Journal on Discrete Mathematics, v.5 n.3, p.366-376, Aug. 1992 [doi>10.1137/0405027]
• 6: Nikhil Bansal , Avrim Blum , Shuchi Chawla, Correlation Clustering, Machine Learning, v.56 n.1-3, p.89-113 [doi>10.1023/B:MACH.0000033116.57574.95]
• 7: J. Bartholdi, C. A. Tovey, and M. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6(2):157--165, 1989.
• 8: J. C. Borda. Mémoire sur les élections au scrutin. Histoire de l'Académie Royale des Sciences, 1781.
• 9: Mao-cheng Cai , Xiaotie Deng , Wenan Zang, An Approximation Algorithm for Feedback Vertex Sets in Tournaments, SIAM Journal on Computing, v.30 n.6, p.1993-2007, 2001 [doi>10.1137/S0097539798338163]
• 10: Moses Charikar , Venkatesan Guruswami , Anthony Wirth, Clustering with Qualitative Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.524, October 11-14, 2003
• 11: M.-J. Condorcet. Éssai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix. 1785.
• 12: P. Diaconis and R. Graham. Spearman's footrule as a measure of disarray. Journal of the Royal Statistical Society, Series B, 39(2):262--268, 1977.
• 13: Irit Dinur , Shmuel Safra, The importance of being biased, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509915]
• 14: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 15: C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank aggregation revisited. 2001. Manuscript.
• 16: G. Even, J. S. Naor, M. Sudan, and B. Schieber. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151--174, 1998.
• 17: Ronald Fagin , Ravi Kumar , D. Sivakumar, Efficient similarity search and classification via rank aggregation, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872795]
• 18: Vladimir Filkov , Steven Skiena, Integrating Microarray Data by Consensus Clustering, Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence, p.418, November 03-05, 2003
• 19: A. Frieze and R. Kannan. Quick approximations to matrices and applications. Combinatorica, 19(2):175--220, 1999.
• 20: Aristides Gionis , Heikki Mannila , Panayiotis Tsaparas, Clustering Aggregation, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.341-352, April 05-08, 2005 [doi>10.1109/ICDE.2005.34]
• 21: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 22: R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85--104. Plenum Press, New York, 1972.
• 23: J. Kemeny and J. Snell. Mathematical Models in the Social Sciences. Blaisdell, New York, 1962. Reprinted by MIT Press, Cambridge, 1972.
• 24: J. G. Kemeny. Mathematics without numbers. Daedalus, 88:571--591, 1959.
• 25: A. Newman. Approximating the maximum acyclic subgraph. Master's thesis, Massachusetts Institute of Technology, Cambridge, MA, June 2000.
• 26: Alantha Newman , Santosh Vempala, Fences Are Futile: On Relaxations for the Linear Ordering Problem, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.333-347, June 13-15, 2001
• 27: C. N. Potts. An algorithm for the single machine sequencing problem with precedence constraints. Mathematical Programming, 13:78--87, 1980.
• 28: P. Seymour. Packing directed circuits fractionally. Combinatorica, 15:281--288, 1995.
• 29: Ewald Speckenmeyer, On Feedback Problems in Diagraphs, Proceedings of the 15th International Workshop on Graph-Theoretic Concepts in Computer Science, p.218-231, June 14-16, 1989
• 30: Alexander Strehl , Joydeep Ghosh, Relationship-based clustering and cluster ensembles for high-dimensional data mining, 2002
• 31: Y. Wakabayashi. The complexity of computing medians of relations. Resenhas, 3(3):323--349, 1998.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
consensus clustering, correlation clustering, minimum feedback arc set, rank aggregation, tournament