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 language | English |
|---|---|
| Pages | 776-782 |
| Number of pages | 7 |
| DOIs | |
| State | Published - 2006 |
| Event | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: Jan 22 2006 → Jan 24 2006 |
Conference
| Conference | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| Country/Territory | United States |
| City | Miami, FL |
| Period | 01/22/06 → 01/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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver