Skip to main navigation Skip to search Skip to main content

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

  • Institute for Defense Analyses
  • Dartmouth College

Research output: Contribution to journalArticlepeer-review

54 Scopus citations

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 + wuv = 1). Special cases of the feedback arc set problem in such weighted tournaments include the feedback arc set problem in un weighted tournaments and rank aggregation. To complement the upper bound, for any constant ε > 0, we exhibit an infinite family of (un weighted) tournaments for which the aforesaid algorithm (irrespective of how ties are broken) has an approximation ratio of 5 - ε.

Original languageEnglish
Article number55
JournalACM Transactions on Algorithms
Volume6
Issue number3
DOIs
StatePublished - Jun 1 2010

Keywords

  • Approximation algorithms
  • Borda-s method
  • Feedback are set problem
  • Rank aggregation
  • Tournaments

Fingerprint

Dive into the research topics of 'Ordering by weighted number of wins gives a good ranking for weighted tournaments'. Together they form a unique fingerprint.

Cite this