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
相关论文
共 50 条
  • [41] Solving the Linear Ordering Problem via A Memetic Algorithm
    Song, Jingyu
    Zhao, Haidan
    Zhou, Taoqin
    Tao, Ye
    Lu, Zhipeng
    PROCEEDINGS OF THE FUTURE TECHNOLOGIES CONFERENCE (FTC) 2018, VOL 2, 2019, 881 : 421 - 430
  • [42] Using pairwise precedences for solving the linear ordering problem
    Santucci, Valentino
    Ceberio, Josu
    APPLIED SOFT COMPUTING, 2020, 87
  • [43] Exact algorithms for weighted and unweighted Borda manipulation problems
    Yang, Yongjie
    Guo, Jiong
    THEORETICAL COMPUTER SCIENCE, 2016, 622 : 79 - 89
  • [44] Approximating the correction of weighted and unweighted orthology and paralogy relations
    Dondi, Riccardo
    Lafond, Manuel
    El-Mabrouk, Nadia
    ALGORITHMS FOR MOLECULAR BIOLOGY, 2017, 12
  • [45] The linear ordering problem with clusters: a new partial ranking
    Alcaraz, Javier
    Garcia-Nove, Eva M.
    Landete, Mercedes
    Monge, Juan F.
    TOP, 2020, 28 (03) : 646 - 671
  • [46] Designing a hybrid genetic algorithm for the linear ordering problem
    Huang, GF
    Lim, A
    GENETIC AND EVOLUTIONARY COMPUTATION - GECCO 2003, PT I, PROCEEDINGS, 2003, 2723 : 1053 - 1064
  • [47] A heuristic framework on a common generalization of the Vehicle Routing Problem and the Linear Ordering Problem
    Blazsik, Zoltan
    Fajfrik, Zoltan Imre
    CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH, 2017, 25 (01) : 55 - 70
  • [48] A heuristic framework on a common generalization of the Vehicle Routing Problem and the Linear Ordering Problem
    Zoltán Blázsik
    Zoltán Imre Fajfrik
    Central European Journal of Operations Research, 2017, 25 : 55 - 70
  • [49] Revised GRASP with path-relinking for the linear ordering problem
    W. Art Chaovalitwongse
    Carlos A. S. Oliveira
    Bruno Chiarini
    Panos M. Pardalos
    Mauricio G. C. Resende
    Journal of Combinatorial Optimization, 2011, 22 : 572 - 593
  • [50] Block-insertion-based algorithms for the linear ordering problem
    Qian, Yanjun
    Lin, Jun
    Li, Dehong
    Hu, Haihua
    COMPUTERS & OPERATIONS RESEARCH, 2020, 115
12345