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

被引：46

作者：

Coppersmith, Don ^{[1
]}

Fleischer, Lisa ^{[2
]}

Rudra, Atri ^{[3
]}

机构：

[1] IDA, Ctr Commun Res, Princeton, NJ 08540 USA

[2] IBM TJ Watson Res Ctr, Yorktown Hts, NY 10598 USA

[3] Univ Washington, Dept Comp Sci & Engn, Seattle, WA 98195 USA

来源：

PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS | 2006年

关键词：

D O I：

10.1145/1109557.1109642

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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

引用

页码：776 / +

页数：2

共 18 条

[1]

Ailon Nir, 2005, P 37 ANN ACM S THEOR, P684, DOI [10.1145/1060590.1060692, DOI 10.1145/1060590.1060692]

[2]

ALON N, SIAM J DISC IN PRESS

[3]

ARORA S, 1996, P 37 ANN S FDN COMP, P24

[4] A POLYNOMIAL ALGORITHM FOR THE 2-PATH PROBLEM FOR SEMICOMPLETE DIGRAPHS [J].

BANGJENSEN, J ;

THOMASSEN, C .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1992, 5 (03) :366-376

[5] VOTING SCHEMES FOR WHICH IT CAN BE DIFFICULT TO TELL WHO WON THE ELECTION [J].

BARTHOLDI, J ;

TOVEY, CA ;

TRICK, MA .

SOCIAL CHOICE AND WELFARE, 1989, 6 (02) :157-165

[6]

BERGER B, 1990, PROCEEDINGS OF THE FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P236

[7]

Borda J.-C., 1781, HIST ACAD ROYAL DES

[8]

CONITZER V, 2005, COMPUTING SLAT UNPUB

[9] SPEARMANS FOOTRULE AS A MEASURE OF DISARRAY [J].

DIACONIS, P ;

GRAHAM, RL .

JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES B-METHODOLOGICAL, 1977, 39 (02) :262-268

[10]

Dinur I, 2002, ANN IEEE SYMP FOUND, P33, DOI 10.1109/SFCS.2002.1181880

← 1 2 →