More Web Proxy on the site http://driver.im/

Article

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

Authors:

Don Coppersmith,

Lisa Fleischer,

Atri RudraAuthors Info & Claims

SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm

Pages 776 - 782

Published: 22 January 2006 Publication History

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

References

[1]

N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: Ranking and clustering. In Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), pages 684--693, 2005.

Digital Library

[2]

N. Alon. Ranking tournaments. In SIAM Journal on Discrete Math, To Appear.

Digital Library

[3]

S. Arora, A. Frieze, and H. Kaplan. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS), pages 24--33, 1996.

Digital Library

[4]

J. Bang-Jensen and C. Thomassen. A polynomial algorithm for 2-path problem in semicomplete graphs. SIAM Journal of Discrete Math, 5(3):366--376, 1992.

Digital Library

[5]

J. J. Bartholdi, C. A. Tovey, and M. A. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6(2):157--165, 1989.

[6]

B. Berger and P. W. Shor. Approximation algorithms for the maximum acyclic subgraph problem. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 236--243, 1990.

Digital Library

[7]

J. C. Borda. Mémoire sur les élections au scrutin. Histoire de l'Académie Royale des Sciences, 1781.

[8]

V. Conitzer. Computing Slater Rankings Using Similarities Among Candidates. Manuscript, 2005. Available at http://www.cs.cmu.edu/~conitzer/slater.pdf

[9]

P. Diaconis and R. Graham. Spearman's footrule as a measure of disarray. Journal of the Royal Statistical Society, Series B, 39(2):262--268, 1977.

[10]

I. Dinur and S. Safra. On the importance of being biased. In Proceedings of the 34th ACM Symposium on Theory of Computing (STOC), pages 33--42, 2002.

Digital Library

[11]

C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank aggregation methods for the web. In Proceedings of the 10th International Conference on the World Wide Web (WWW10), pages 613--622, 2001.

Digital Library

[12]

G. Even, J. S. Naor, M. Sudan, and B. Schieber. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151--174, 1998.

[13]

R. Fagin, R. Kumar, M. Mahdian, D. Sivakumar, and E. Vee. Rank Aggregation: An Algorithmic Perspective. Unpublished Manuscript, 2005.

[14]

R. Hassin and S. Rubinstein. Approximations for the maximum acyclic subgraph problem. Information Processing Letters, 51:133--140, 1977.

Digital Library

[15]

R. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, pages 85--104, 1972.

[16]

C. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer System Science, 43:425--440, 1991.

[17]

P. Seymour. Packing directed circuits fractionally. Combinatorica, 15(2):281--288, 1995.

[18]

A. van Zuylen. Deterministic approximation algorithms for ranking and clusterings. Cornell ORIE Tech Report No. 1431, 2005.

Cited By

Colombo PNoiry NIrurozki EClémençon SKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)What are the best systems? new perspectives on NLP benchmarkingProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602221(26915-26932)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3602221
Rajpal SParameswaran ACuzzocrea AAllan JPaton NSrivastava DAgrawal RBroder AZaki MCandan SLabrinidis ASchuster AWang H(2018)Holistic Crowd-Powered Sorting via AIDProceedings of the 27th ACM International Conference on Information and Knowledge Management10.1145/3269206.3269279(1607-1610)Online publication date: 17-Oct-2018
https://dl.acm.org/doi/10.1145/3269206.3269279
Shen JXiao JHe XShang JSinha SHan JCollins-Thompson KMei QDavison BLiu YYilmaz E(2018)Entity Set Search of Scientific LiteratureThe 41st International ACM SIGIR Conference on Research & Development in Information Retrieval10.1145/3209978.3210055(565-574)Online publication date: 27-Jun-2018
https://dl.acm.org/doi/10.1145/3209978.3210055
Show More Cited By

Recommendations

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

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 ...
On the number of cycles in local tournaments

A digraph without loops, multiple arcs and directed cycles of length two is called a local tournament if the set of in-neighbors as well as the set of out-neighbors of every vertex induces a tournament. A vertex of a strongly connected digraph is called ...
The number of -free vertices on 3-partite tournaments

Let T be a 3-partite tournament. We say that a vertex v is C"3@?-free if v does not lie on any directed triangle of T. Let F"3(T) be the set of the C"3@?-free vertices in a 3-partite tournament and f"3(T) its cardinality. In this paper we prove that if ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm

January 2006

1261 pages

ISBN:0898716055

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
509
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Colombo PNoiry NIrurozki EClémençon SKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)What are the best systems? new perspectives on NLP benchmarkingProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602221(26915-26932)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3602221
Rajpal SParameswaran ACuzzocrea AAllan JPaton NSrivastava DAgrawal RBroder AZaki MCandan SLabrinidis ASchuster AWang H(2018)Holistic Crowd-Powered Sorting via AIDProceedings of the 27th ACM International Conference on Information and Knowledge Management10.1145/3269206.3269279(1607-1610)Online publication date: 17-Oct-2018
https://dl.acm.org/doi/10.1145/3269206.3269279
Shen JXiao JHe XShang JSinha SHan JCollins-Thompson KMei QDavison BLiu YYilmaz E(2018)Entity Set Search of Scientific LiteratureThe 41st International ACM SIGIR Conference on Research & Development in Information Retrieval10.1145/3209978.3210055(565-574)Online publication date: 27-Jun-2018
https://dl.acm.org/doi/10.1145/3209978.3210055
Brancotte BYang BBlin GCohen-Boulakia SDenise AHamel S(2015)Rank aggregation with tiesProceedings of the VLDB Endowment10.14778/2809974.28099828:11(1202-1213)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.14778/2809974.2809982
Pal A(2015)Metrics and Algorithms for Routing Questions to User CommunitiesACM Transactions on Information Systems10.1145/272470633:3(1-29)Online publication date: 9-Mar-2015
https://dl.acm.org/doi/10.1145/2724706
Perez A(2015)On the kernelization of ranking r -CSPsDiscrete Applied Mathematics10.1016/j.dam.2015.01.032186:C(214-225)Online publication date: 11-May-2015
https://dl.acm.org/doi/10.1016/j.dam.2015.01.032
Elkind EShah N(2014)Electing the most probable without eliminating the irrationalProceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence10.5555/3020751.3020771(182-191)Online publication date: 23-Jul-2014
https://dl.acm.org/doi/10.5555/3020751.3020771
Liu CZhang KXiong HJiang GYang QMacskassy SPerlich CLeskovec JWang WGhani R(2014)Temporal skeletonization on sequential dataProceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/2623330.2623741(1336-1345)Online publication date: 24-Aug-2014
https://dl.acm.org/doi/10.1145/2623330.2623741
Caragiannis IKaklamanis CKaranikolas NProcaccia A(2014)Socially desirable approximations for dodgson’s voting ruleACM Transactions on Algorithms10.1145/255695010:2(1-28)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1145/2556950
Pal AWang FZhou MNichols JSmith BHe QIyengar ANejdl WPei JRastogi R(2013)Question routing to user communitiesProceedings of the 22nd ACM international conference on Information & Knowledge Management10.1145/2505515.2505669(2357-2362)Online publication date: 27-Oct-2013
https://dl.acm.org/doi/10.1145/2505515.2505669
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents