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 条
[81]  
Erdos P., 1964, Magyar Tud. Akad. Mat. Kutato Int. Kozl., V9, P125
[82]  
Erdos P., 1965, CANAD MATH B, V8, P269, DOI DOI 10.4153/CMB-1965-017-1
[83]   Approximating minimum feedback sets and multicuts in directed graphs [J].
Even, G ;
Naor, J ;
Schieber, B ;
Sudan, M .
ALGORITHMICA, 1998, 20 (02) :151-174
[84]   Determining the automorphism group of the linear ordering polytope [J].
Fiorini, S .
DISCRETE APPLIED MATHEMATICS, 2001, 112 (1-3) :121-128
[85]   Facets of linear signed order polytopes [J].
Fiorini, S ;
Fishburn, P .
DISCRETE APPLIED MATHEMATICS, 2003, 131 (03) :597-610
[86]   How to recycle your facets [J].
Fiorini, Samuel .
DISCRETE OPTIMIZATION, 2006, 3 (02) :136-153
[87]   INDUCED BINARY PROBABILITIES AND THE LINEAR ORDERING POLYTOPE - A STATUS-REPORT [J].
FISHBURN, PC .
MATHEMATICAL SOCIAL SCIENCES, 1992, 23 (01) :67-80
[88]   CONDORCET SOCIAL CHOICE FUNCTIONS [J].
FISHBURN, PC .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 33 (03) :469-489
[89]   EXACT AND HEURISTIC ALGORITHMS FOR THE WEIGHTED FEEDBACK ARC SET PROBLEM - A SPECIAL CASE OF THE SKEW-SYMMETRIC QUADRATIC ASSIGNMENT PROBLEM [J].
FLOOD, MM .
NETWORKS, 1990, 20 (01) :1-23
[90]   BRANCH SEARCH ALGORITHM FOR MAXIMUM LIKELIHOOD PAIRED COMPARISON RANKING [J].
FLUECK, JA ;
KORSH, JF .
BIOMETRIKA, 1974, 61 (03) :621-626
45678910111213