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 language | English |
|---|---|
| Article number | 55 |
| Journal | ACM Transactions on Algorithms |
| Volume | 6 |
| Issue number | 3 |
| DOIs | |
| State | Published - 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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver