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 条
[51]  
Charon I., 1992, MATH INF SCI HUM, V119, P53
[52]   A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments [J].
Charon, Irene ;
Hudry, Olivier .
DISCRETE APPLIED MATHEMATICS, 2006, 154 (15) :2097-2116
[53]  
CHARTRAND G, 1971, J COMB THEORY B, V10, P12
[54]   Algorithmic aspects of using small instance relaxations in parallel branch-and-cut [J].
Christof, T ;
Reinelt, G .
ALGORITHMICA, 2001, 30 (04) :597-629
[55]  
Christof T., 1996, Top, V4, P1
[56]  
CHRISTOF T, 1997, LOW DIMENSIONAL LINE
[57]   The biorder polytope [J].
Christophe, J ;
Doignon, JP ;
Fiorini, S .
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2004, 21 (01) :61-82
[58]   Learning to order things [J].
Cohen, WW ;
Schapire, RE ;
Singer, Y .
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 1999, 10 :243-270
[59]  
Condorcet M. J, 1785, ESSAI APPL ANAL PROB
[60]  
Congram R.K., 2000, THESIS U SOUTHAMPTON
12345678910