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 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.

REFERENCES

• 1: Ailon, N. 2008. Aggregation of partial rankings, p-ratings and top-m lists. Algorithmica. DOI 10.1007/s00453-008-9211-1.
• 2: Nir Ailon , Moses Charikar, Fitting tree metrics: Hierarchical clustering and Phylogeny, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.73-82, October 23-25, 2005 [doi>10.1109/SFCS.2005.36]
• 3: Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: ranking and clustering, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060692]
• 4: Ailon, N., and Mohri, M. 2008. An efficient reduction of ranking to classification. In Conference on Learning Theory (COLT) (Helsinki, Finland).
• 5: Noga Alon, Ranking Tournaments, SIAM Journal on Discrete Mathematics, v.20 n.1, p.137-142, 2006 [doi>10.1137/050623905]
• 6: Alon, N., and Spencer, J. H. 1992. The Probabilistic Method. Wiley, New York.
• 7: 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
• 8: Balcan, M.-F., Bansal, N., Beygelzimer, A., Coppersmith, D., Langford, J., and Sorkin, G. B. 2007. Robust reductions from ranking to classification. In Proceedings of the Conference on Learning Theory (COLT). Lecture Notes in Computer Science, vol. 4539. Springer-Verlag, New York, 604--619.
• 9: 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]
• 10: 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]
• 11: Bartholdi, J., Tovey, C. A., and Trick, M. 1989. Voting schemes for which it can be difficult to tell who won the election. Social Choice Welf. 6, 2, 157--165.
• 12: Borda, J. C. 1781. Mémoire sur les élections au scrutin. Histoire de l'Académie Royale des Sciences.
• 13: 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]
• 14: 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
• 15: Kamalika Chaudhuri , Kevin Chen , Radu Mihaescu , Satish Rao, On the tandem duplication-random loss model of genome rearrangement, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.564-570, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109619]
• 16: Condorcet, M.-J. 1785. Éssai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix.
• 17: Don Coppersmith , Lisa Fleischer , Atri Rudra, Ordering by weighted number of wins gives a good ranking for weighted tournaments, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.776-782, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109642]
• 18: Diaconis, P., and Graham, R. 1977. Spearman's footrule as a measure of disarray. J. Roy. Stat. Soc., Ser. B 39, 2, 262--268.
• 19: 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]
• 20: 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]
• 21: Dwork, C., Kumar, R., Naor, M., and Sivakumar, D. 2001b. Rank aggregation revisited. Manuscript. (Available from: http://www.eecs.harvard.edu/~michaelm/CS222/rank2.pdf.)
• 22: Even, G., Naor, J. S., Sudan, M., and Schieber, B. 1998. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20, 2, 151--174.
• 23: 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]
• 24: 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
• 25: Frieze, A., and Kannan, R. 1999. Quick approximations to matrices and applications. Combinatorica 19, 2, 175--220.
• 26: Aristides Gionis , Heikki Mannila , Panayiotis Tsaparas, Clustering Aggregation, Proceedings of the 21st International Conference on Data Engineering, p.341-352, April 05-08, 2005 [doi>10.1109/ICDE.2005.34]
• 27: 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]
• 28: Karp, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. Plenum Press, New York, 85--104.
• 29: Kemeny, J. G. 1959. Mathematics without numbers. Daedalus 88, 571--591.
• 30: Kemeny, J., and Snell, J. 1962. Mathematical Models in the Social Sciences. Blaisdell, New York. (Reprinted by MIT Press, Cambridge, 1972.)
• 31: Claire Kenyon-Mathieu , Warren Schudy, How to rank with few errors, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250806]
• 32: Newman, A. 2000. Approximating the maximum acyclic subgraph. M.S. thesis, Massachusetts Institute of Technology, Cambridge, MA.
• 33: 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
• 34: Potts, C. N. 1980. An algorithm for the single machine sequencing problem with precedence constraints. Math. Prog. 13, 78--87.
• 35: Seymour, P. 1995. Packing directed circuits fractionally. Combinatorica 15, 281--288.
• 36: E. Speckenmeyer, On feedback problems in digraphs, Proceedings of the fifteenth international workshop on Graph-theoretic concepts in computer science, p.218-231, March 1990, Castle Rolduc, The Netherlands
• 37: Strehl, A. 2002. PhD dissertation. Ph.D. thesis, University of Texas at Austin.
• 38: Wakabayashi, Y. 1998. The complexity of computing medians of relations. Resenhas 3, 3, 323--349.
• 39: Williamson, D. P., and van Zuylen, A. 2007. Deterministic algorithms for rank aggregation and other ranking and clustering problems. In Proceedings of the 5th Workshop on Approximation and Online Algorithms (WAOA).

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory

Keywords:
Rank aggregation, consensus clustering, correlation clustering, minimum feedback arc-set, tournaments