How to rank with few errors

ABSTRACT

We present a polynomial time approximation scheme (PTAS) for the minimum feedback arc set problem on tournaments. A simple weighted generalization gives a PTAS for Kemeny-Young rank aggregation.

REFERENCES

• 1: 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]
• 2: Nir Ailon. Aggregation of Partial Rankings, p-Ratings and Top-m Lists. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, to appear.
• 3: Noga Alon, Ranking Tournaments, SIAM Journal on Discrete Mathematics, v.20 n.1, p.137-142, 2006 [doi>10.1137/050623905]
• 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: F.B.Baker and L.J.Hubert, Applications of combinatorial programming to data analysis: seriation using asymmetric proximity measures, British J. Math. Statis. Psych. 30 (1977) 154--164.
• 6: J. Borda. Memoire sur les elections au scrutin. Histoire de l'Academie Royale des Sciences, 1781.
• 7: 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]
• 8: 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
• 9: William W. Cohen , Robert E. Schapire , Yoram Singer, Learning to order things, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.451-457, July 1998, Denver, Colorado, United States
• 10: M. Condorcet. Essai sur l'application de l'analyse 'a la probabilite des decisions rendues 'a la pluralite des voix. 1785.
• 11: Conitzer, V. Computing Slater Rankings Using Similarities Among Candidates. Proceedings of the 21st National Conference on Artificial Intelligence (AAAI-06), Boston, MA, USA, 613--619. 2006.
• 12: 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]
• 13: C. Demetrescu and I. Finocchi. Break the "right" cycles and get the "best" drawing. In B.E. Moret and A.V. Goldberg, editors, Proceedings of the 2nd International Workshop on Algorithmic Engineering and Experiments (ALENEX), 171--182, 2000.
• 14: P. Diaconis and R. Graham. Spearman's footrule as a measure of disarray. J. of the Royal Statistical Society, 39(2), pages 262--268, 1977.
• 15: 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]
• 16: Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar. Rank aggregation revisited. Manuscript. 2001.
• 17: Cynthia Dwork, Ravi Kumar, Moni Naor, D. Sivakumar. Rank Aggregation Methods for the Web. WWW10. 2001.
• 18: P. Erdös and J.W.Moon, On sets on consistent arcs in tournaments, Canadian Mathematical Bulletin 8 (1965) 269--271.
• 19: G. Even , J. Naor , S. Rao , B. Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.62, October 23-25, 1995
• 20: Fernandez de la Vega, W. On the maximal cardinality of a consistent set of arcs in a random tournament, J. Combinatorial Theory, Ser. B 35:328--332 (1983).
• 21: M.M.Flood. Exact and Heuristic Algorithms for the Weighted Feedback Arc Set Problem: a Special Case of the Skew-Symmetric Quadratic Assignment Problem. Networks, 20:1--23, 1990.
• 22: Alan M. Frieze, Ravi Kannan: Quick Approximation to Matrices and Applications. Combinatorica 19(2): 175--220 (1999).
• 23: M. Grötschel, M. Junger, G. Reinelt. Facets of the linear ordering polytope. Math. Programming 33, 1985, 43--60.
• 24: M. Grötschel, M. Junger, G. Reinelt. On the acyclic subgraph polytope. Math. Programming 33, 1985, 28--42.
• 25: Refael Hassin , Shlomi Rubinstein, Approximations for the maximum acyclic subgraph problem, Information Processing Letters, v.51 n.3, p.133-140, Aug. 10, 1994 [doi>10.1016/0020-0190(94)00086-7]
• 26: H.A. Jung, On subgraphs without cycles in tournaments, Combinatorial Theory and its Applications II, North Holland (1970) 675--677.
• 27: M. Junger, Polyhedral combinatorics and the Acyclic Subdigraph Problem (Heldermann Verlag, Berlin, 1985).
• 28: Karp, R., 1972. Reducibility among combinatorial problems. In: Miller, R. E., Thatcher, J. W. (Eds.), Complexity of Computer Computations. Plenum Press, NY, pp. 85--103.
• 29: J. Kemeny. Mathematics without numbers. Daedalus, 88:571--591, 1959.
• 30: J. Kemeny and J. Snell. Mathematical models in the social sciences. Blaisdell, New York, 1962. Reprinted by MIT press, Cambridge, 1972.
• 31: Claire Kenyon-Mathieu and Warren Schudy. How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments ECCC Report TR06-144, Nov 2006.
• 32: B. Korte, Approximative algorithms for discrete optimization problems, Ann. Discrete Math 4 (1979), 85--120.
• 33: T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 422--431. IEEE, October 1988.
• 34: A. Lempel and I. Cederbaum. Minimum feedback arc and vertex set of a directed graph. IEEE Trans. Circuit Theory, 13(4): 399--403, 1966.
• 35: K.B.Reid, On sets of arcs containing no cycles in tournaments, Canad. Math Bulletin 12 (1969) 261--264.
• 36: K.D.Reid and E.T.Parker, Disproof of a conjecture of Erdös and Moser on tournaments, J. Combin. Theory 9 (1970) 225--238.
• 37: S. Seshu and M.B. Reed, Linear Graphs and Electrical Networks, Addison-Wesley, Reading, MA, 1961. Attribute the problem of the minimum feedback arc set to Runyon.
• 38: P.D. Seymour. Packing directed circuit fractionally. Combinatorica 15:281--288, 1995.
• 39: P. Slater, Inconsistencies in a schedule of paired comparisons, Biometrika 48 (1961) 303--312.
• 40: J. Spencer, Optimal ranking of tournaments, Networks 1(1971) 135--138.
• 41: J. Spencer, Optimal ranking of unrankable tournaments, Period. Math. Hungar. 11-2 (1980) 131--144.
• 42: K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern., 11(2):109--125, 1981.
• 43: A.W.Tucker. On directed graphs and integer programs. Presented at 1960 Symposium on Combinatorial Problems, Princeton University, cited in {44}.
• 44: D.H. Younger. Minimum feedback arc sets for a directed graph. IEEE Trans. Circuit Theory 10 (1963), 238--245.
• 45: A. van Zuylen. Deterministic approximation algorithms for ranking and clusterings. Cornell ORIE Tech report No. 1431. 2005.
• 46: Anke van Zuylen and Rajneesh Hegde and Kamal Jain and David P. Williamson Deterministic pivoting algorithms for constrained ranking and clustering problems. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, to appear.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
Kemeny-Young rank aggregation, approximation algorithm, feedback arc set, max acyclic subgraph, polynomial-time approximation scheme, tournament graphs