About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 2006
Conference paper
Ordering by weighted number of wins gives a good ranking for weighted tournaments
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 - ε.