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 条
[1]   On the maximum number of Hamiltonian paths in tournaments [J].
Adler, I ;
Alon, N ;
Ross, SM .
RANDOM STRUCTURES & ALGORITHMS, 2001, 18 (03) :291-296
[2]  
Ailon Nir, 2005, P 37 ANN ACM S THEOR, P684, DOI [10.1145/1060590.1060692, DOI 10.1145/1060590.1060692]
[3]   ON THE MINIMUM VIOLATIONS RANKING OF A TOURNAMENT [J].
ALI, I ;
COOK, WD ;
KRESS, M .
MANAGEMENT SCIENCE, 1986, 32 (06) :660-672
[4]   Ranking tournaments [J].
Alon, N .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2006, 20 (01) :137-142
[5]   THE MAXIMUM NUMBER OF HAMILTONIAN PATHS IN TOURNAMENTS [J].
ALON, N .
COMBINATORICA, 1990, 10 (04) :319-324
[6]  
Alon N., 2004, The probabilistic method
[7]   A COMBINATORIAL PROOF OF A CONJECTURE OF GOLDBERG AND MOON [J].
ALSPACH, B .
CANADIAN MATHEMATICAL BULLETIN, 1968, 11 (05) :655-&
[8]   CYCLES OF EACH LENGTH IN REGULAR TOURNAMENTS [J].
ALSPACH, B .
CANADIAN MATHEMATICAL BULLETIN, 1967, 10 (02) :283-&
[9]  
[Anonymous], THESIS CAMBRIDGE U C
[10]  
[Anonymous], RECENT ADV MATRIX TH
12345678910