Ordering by weighted number of wins gives a good ranking for weighted tournaments

ABSTRACT

We consider the following simple algorithm for feedback arc set problem in weighted tournaments --- order the vertices by their weighted indegrees. We show that this algorithm has an approximation guarantee of 5 if the weights satisfy probability constraints (for any pair of vertices u and v, wuv + wvu = 1). Special cases of feedback arc set problem in such weighted tournaments include feedback arc set problem in unweighted tournaments and rank aggregation. Finally, for any constant ε > 0, we exhibit an infinite family of (unweighted) tournaments for which the above algorithm (irrespective of how ties are broken) has an approximation ratio of 5 - ε.

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: Noga Alon, Ranking Tournaments, SIAM Journal on Discrete Mathematics, v.20 n.1, p.137-142, 2006 [doi>10.1137/050623905]
• 3: 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
• 4: 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]
• 5: J. J. Bartholdi, C. A. Tovey, and M. A. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6(2):157--165, 1989.
• 6: Bonnie Berger , Peter W. Shor, Approximation alogorithms for the maximum acyclic subgraph problem, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.236-243, January 22-24, 1990, San Francisco, California, United States
• 7: J. C. Borda. Mémoire sur les élections au scrutin. Histoire de l'Académie Royale des Sciences, 1781.
• 8: V. Conitzer. Computing Slater Rankings Using Similarities Among Candidates. Manuscript, 2005. Available at http://www.cs.cmu.edu/~conitzer/slater.pdf
• 9: 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.
• 10: 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]
• 11: 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]
• 12: 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.
• 13: R. Fagin, R. Kumar, M. Mahdian, D. Sivakumar, and E. Vee. Rank Aggregation: An Algorithmic Perspective. Unpublished Manuscript, 2005.
• 14: 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]
• 15: R. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, pages 85--104, 1972.
• 16: C. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer System Science, 43:425--440, 1991.
• 17: P. Seymour. Packing directed circuits fractionally. Combinatorica, 15(2):281--288, 1995.
• 18: A. van Zuylen. Deterministic approximation algorithms for ranking and clusterings. Cornell ORIE Tech Report No. 1431, 2005.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Sequencing and scheduling

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory