ECCC-Report TR05-131https://eccc.weizmann.ac.il/report/2005/131Comments and Revisions published for TR05-131en-usThu, 10 Nov 2005 22:09:36 +0200
Paper TR05-131
| Ordering by weighted number of wins gives a good ranking for weighted tournaments |
Don Coppersmith,
Lisa Fleischer,
Atri Rudra
https://eccc.weizmann.ac.il/report/2005/131We 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 \textit{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 $\epsilon>0$, we exhibit an infinite family of (unweighted) tournaments for which the above algorithm ({\em irrespective} of how ties are broken) has an approximation ratio of $5-\epsilon$.
Thu, 10 Nov 2005 22:09:36 +0200https://eccc.weizmann.ac.il/report/2005/131