{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T14:36:12Z","timestamp":1777041372654,"version":"3.51.4"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2008,10,1]],"date-time":"2008-10-01T00:00:00Z","timestamp":1222819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0205594"],"award-info":[{"award-number":["CCR-0205594"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0237113"],"award-info":[{"award-number":["CCR-0237113"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-FG02-02ER25540"],"award-info":[{"award-number":["DE-FG02-02ER25540"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,10]]},"abstract":"<jats:p>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\u2286BPP, there is no polynomial time algorithm for the problem of minimum feedback arc set in tournaments.<\/jats:p>","DOI":"10.1145\/1411509.1411513","type":"journal-article","created":{"date-parts":[[2008,11,6]],"date-time":"2008-11-06T13:49:43Z","timestamp":1225979383000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":352,"title":["Aggregating inconsistent information"],"prefix":"10.1145","volume":"55","author":[{"given":"Nir","family":"Ailon","sequence":"first","affiliation":[{"name":"Google Research, New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moses","family":"Charikar","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alantha","family":"Newman","sequence":"additional","affiliation":[{"name":"DIMACS, Rutgers University, New Brunswick, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,11,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1718470.1718475"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.36"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060692"},{"key":"e_1_2_1_4_1","volume-title":"Conference on Learning Theory (COLT)","author":"Ailon N.","unstructured":"Ailon , N. , and Mohri , M . 2008. An efficient reduction of ranking to classification . In Conference on Learning Theory (COLT) ( Helsinki, Finland). Ailon, N., and Mohri, M. 2008. An efficient reduction of ranking to classification. In Conference on Learning Theory (COLT) (Helsinki, Finland)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/050623905"},{"key":"e_1_2_1_6_1","unstructured":"Alon N. and Spencer J. H. 1992. The Probabilistic Method. Wiley New York.  Alon N. and Spencer J. H. 1992. The Probabilistic Method. Wiley New York."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 37th Annual Symposium on the Foundations of Computer Science (FOCS)","author":"Arora S.","unstructured":"Arora , S. , Frieze , A. , and Kaplan , H . 1996. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems . In Proceedings of the 37th Annual Symposium on the Foundations of Computer Science (FOCS) ( Burlington, VT). IEEE Computer Society Press, Los Alamitos, CA, 24--33. Arora, S., Frieze, A., and Kaplan, H. 1996. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. In Proceedings of the 37th Annual Symposium on the Foundations of Computer Science (FOCS) (Burlington, VT). IEEE Computer Society Press, Los Alamitos, CA, 24--33."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Conference on Learning Theory (COLT). Lecture Notes in Computer Science","volume":"4539","author":"Balcan M.-F.","unstructured":"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. 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."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405027"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033116.57574.95"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00303169"},{"key":"e_1_2_1_12_1","unstructured":"Borda J. C. 1781. M\u00e9moire sur les \u00e9lections au scrutin. Histoire de l'Acad\u00e9mie Royale des Sciences.  Borda J. C. 1781. M\u00e9moire sur les \u00e9lections au scrutin. Histoire de l'Acad\u00e9mie Royale des Sciences."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798338163"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Charikar M.","unstructured":"Charikar , M. , Guruswami , V. , and Wirth , A . 2003. Clustering with qualitative information . In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS) ( Boston, MA). IEEE Computer Society Press, Los Alamitos, CA, 524--533. Charikar, M., Guruswami, V., and Wirth, A. 2003. Clustering with qualitative information. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (Boston, MA). IEEE Computer Society Press, Los Alamitos, CA, 524--533."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA'06)","author":"Chaudhuri K.","unstructured":"Chaudhuri , K. , Chen , K. , Mihaescu , R. , and Rao , S . 2006. On the tandem duplication-random loss model of genome rearrangement . In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA'06) . ACM, New York, 564--570. Chaudhuri, K., Chen, K., Mihaescu, R., and Rao, S. 2006. On the tandem duplication-random loss model of genome rearrangement. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA'06). ACM, New York, 564--570."},{"key":"e_1_2_1_16_1","unstructured":"Condorcet M.-J. 1785. \u00c9ssai sur l'application de l'analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix.  Condorcet M.-J. 1785. \u00c9ssai sur l'application de l'analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA'06)","author":"Coppersmith D.","unstructured":"Coppersmith , D. , Fleischer , L. , and Rudra , A . 2006. Ordering by weighted number of wins gives a good ranking for weighted tournaments . In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA'06) . ACM, New York, 776--782. Coppersmith, D., Fleischer, L., and Rudra, A. 2006. Ordering by weighted number of wins gives a good ranking for weighted tournaments. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA'06). ACM, New York, 776--782."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1977.tb01624.x"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509915"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/371920.372165"},{"key":"e_1_2_1_21_1","unstructured":"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.)  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.)"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872795"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of International Conference on Tools with Artificial Intelligence (ICTAI)","author":"Filkov V.","unstructured":"Filkov , V. , and Skiena , S . 2003. Integrating microarray data by consensus clustering . In Proceedings of International Conference on Tools with Artificial Intelligence (ICTAI) ( Sacramento, CA). 418--425. Filkov, V., and Skiena, S. 2003. Integrating microarray data by consensus clustering. In Proceedings of International Conference on Tools with Artificial Intelligence (ICTAI) (Sacramento, CA). 418--425."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.34"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_28_1","volume-title":"Complexity of Computer Computations","author":"Karp R. M.","unstructured":"Karp , R. M. 1972. Reducibility among combinatorial problems . In Complexity of Computer Computations . Plenum Press , New York , 85--104. Karp, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. Plenum Press, New York, 85--104."},{"key":"e_1_2_1_29_1","first-page":"571","article-title":"Mathematics without numbers","volume":"88","author":"Kemeny J. G.","year":"1959","unstructured":"Kemeny , J. G. 1959 . Mathematics without numbers . Daedalus 88 , 571 -- 591 . Kemeny, J. G. 1959. Mathematics without numbers. Daedalus 88, 571--591.","journal-title":"Daedalus"},{"key":"e_1_2_1_30_1","volume-title":"Cambridge","author":"Kemeny J.","year":"1972","unstructured":"Kemeny , J. , and Snell , J . 1962. Mathematical Models in the Social Sciences. Blaisdell, New York. (Reprinted by MIT Press , Cambridge , 1972 .) Kemeny, J., and Snell, J. 1962. Mathematical Models in the Social Sciences. Blaisdell, New York. (Reprinted by MIT Press, Cambridge, 1972.)"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250806"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization (IPCO). 333--347","author":"Newman A.","unstructured":"Newman , A. , and Vempala , S . 2001. Fences are futile: On relaxations for the linear ordering problem . In Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization (IPCO). 333--347 . Newman, A., and Vempala, S. 2001. Fences are futile: On relaxations for the linear ordering problem. In Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization (IPCO). 333--347."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120909"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"},{"key":"e_1_2_1_36_1","series-title":"Lecture Notes in Computer Science","volume-title":"On feedback problems in digraphs. Graph Theoretic Concepts in Computer Science","author":"Speckenmeyer E.","unstructured":"Speckenmeyer , E. 1989. On feedback problems in digraphs. Graph Theoretic Concepts in Computer Science , Lecture Notes in Computer Science , vol. 411 , Springer-Verlag , New York , 218--231. Speckenmeyer, E. 1989. On feedback problems in digraphs. Graph Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 411, Springer-Verlag, New York, 218--231."},{"key":"e_1_2_1_37_1","unstructured":"Strehl A. 2002. PhD dissertation. Ph.D. thesis University of Texas at Austin.  Strehl A. 2002. PhD dissertation. Ph.D. thesis University of Texas at Austin."},{"key":"e_1_2_1_38_1","first-page":"323","article-title":"The complexity of computing medians of relations","volume":"3","author":"Wakabayashi Y.","year":"1998","unstructured":"Wakabayashi , Y. 1998 . The complexity of computing medians of relations . Resenhas 3 , 3, 323 -- 349 . Wakabayashi, Y. 1998. The complexity of computing medians of relations. Resenhas 3, 3, 323--349.","journal-title":"Resenhas"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 5th Workshop on Approximation and Online Algorithms (WAOA).","author":"Williamson D. P.","year":"2007","unstructured":"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). 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)."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1411509.1411513","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1411509.1411513","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:29Z","timestamp":1750253369000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1411509.1411513"}},"subtitle":["Ranking and clustering"],"short-title":[],"issued":{"date-parts":[[2008,10]]},"references-count":38,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["10.1145\/1411509.1411513"],"URL":"https:\/\/doi.org\/10.1145\/1411509.1411513","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10]]},"assertion":[{"value":"2006-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}