Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-131 | 7th November 2005 00:00

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

RSS-Feed

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 \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.



ISSN 1433-8092 | Imprint