A survey on the linear ordering problem for weighted or unweighted tournaments

被引：37
作者：
Charon, Irene [1 ]
Hudry, Olivier [1 ]
机构：
[1] Ecole Natl Super Telecommun Bretagne, FR-75634 Paris 13, France
来源：
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH | 2007年 / 5卷 / 01期
关键词：
aggregation of preferences; voting theory; social choice; linear ordering problem; Kemeny's problem; Slater's problem; median order; reversing set; feedback arc set; acyclic subgraph; optimal triangulation; graph theory; tournament solutions; complexity; combinatorial optimization; combinatorics;
D O I：
10.1007/s10288-007-0036-6
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
In this paper, we survey some results, conjectures and open problems dealing with the combinatorial and algorithmic aspects of the linear ordering problem. This problem consists in finding a linear order which is at minimum distance from a (weighted or not) tournament. We show how it can be used to model an aggregation problem consisting of going from individual preferences defined on a set of candidates to a collective ranking of these candidates.
引用
收藏
页码：5 / 60
页数：56
相关论文
共 252 条
[61]   Ranking players in multiple tournaments [J].
Cook, WD ;
Doyle, J ;
Green, R ;
Kress, M .
COMPUTERS & OPERATIONS RESEARCH, 1996, 23 (09) :869-880
[62]   HEURISTICS FOR RANKING PLAYERS IN A ROUND ROBIN TOURNAMENT [J].
COOK, WD ;
GOLAN, I ;
KRESS, M .
COMPUTERS & OPERATIONS RESEARCH, 1988, 15 (02) :135-144
[63]  
Cook WD, 1976, CAHIERS CTR ETUDES R, V18, P337
[64]  
Copeland A.H., 1951, A reasonable social welfare function
[65]   MATRIX MULTIPLICATION VIA ARITHMETIC PROGRESSIONS [J].
COPPERSMITH, D ;
WINOGRAD, S .
JOURNAL OF SYMBOLIC COMPUTATION, 1990, 9 (03) :251-280
[66]   Ordering by weighted number of wins gives a good ranking for weighted tournaments [J].
Coppersmith, Don ;
Fleischer, Lisa ;
Rudra, Atri .
PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, :776-+
[67]   Constructive quasi-Ramsey numbers and tournament ranking [J].
Czygrinow, A ;
Poljak, S ;
Rödl, V .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (01) :48-63
[68]  
Davenport A, 2004, PROCEEDING OF THE NINETEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND THE SIXTEENTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE, P697
[69]  
de Borda JC., 1784, MEMOIRE ELECTIONS SC
[70]  
Debord B., 1987, MATH SCI HUMAINES, V97, P5
234567891011