Skip to main navigation Skip to search Skip to main content

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

  • IDA
  • IBM

Research output: Contribution to conferencePaperpeer-review

101 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, w uv + w vu = 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 - ε.

Original languageEnglish
Pages776-782
Number of pages7
DOIs
StatePublished - 2006
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: Jan 22 2006Jan 24 2006

Conference

ConferenceSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityMiami, FL
Period01/22/0601/24/06

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