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 条
  • [31] On VLSI interconnect optimization and linear ordering problem
    Wimer, Shmuel
    Moiseev, Konstantin
    Kolodny, Avinoam
    OPTIMIZATION AND ENGINEERING, 2011, 12 (04) : 603 - 609
  • [32] MODELING HIERARCHY - TRANSITIVITY AND THE LINEAR ORDERING PROBLEM
    ROBERTS, JM
    JOURNAL OF MATHEMATICAL SOCIOLOGY, 1990, 16 (01) : 77 - 87
  • [33] On VLSI interconnect optimization and linear ordering problem
    Shmuel Wimer
    Konstantin Moiseev
    Avinoam Kolodny
    Optimization and Engineering, 2011, 12 : 603 - 609
  • [34] Integer linear programming models for the weighted total domination problem
    Ma, Yuede
    Cai, Qingqiong
    Yao, Shunyu
    APPLIED MATHEMATICS AND COMPUTATION, 2019, 358 : 146 - 150
  • [35] A branch-and-bound algorithm for the linear ordering problem with cumulative costs
    Righini, Giovanni
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 186 (03) : 965 - 971
  • [36] The linear ordering problem with clusters: a new partial ranking
    Javier Alcaraz
    Eva M. García-Nové
    Mercedes Landete
    Juan F. Monge
    TOP, 2020, 28 : 646 - 671
  • [37] An efficient tabu search algorithm for the linear ordering problem
    Sakabe, Masahiro
    Yagiura, Mutsunori
    JOURNAL OF ADVANCED MECHANICAL DESIGN SYSTEMS AND MANUFACTURING, 2022, 16 (04):
  • [38] Implementing Artificial Immune Systems for the Linear Ordering Problem
    Kroemer, Pavel
    Platos, Jan
    Snasel, Vaclav
    SOFT COMPUTING MODELS IN INDUSTRIAL AND ENVIRONMENTAL APPLICATIONS, 2013, 188 : 53 - 62
  • [39] Efficient local search algorithms for the linear ordering problem
    Sakuraba, Celso S.
    Yagiura, Mutsunori
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2010, 17 (06) : 711 - 737
  • [40] A Genetic Programming Approach for Solving the Linear Ordering Problem
    Pop, P. C.
    Matei, O.
    HYBRID ARTIFICIAL INTELLIGENT SYSTEMS, PT II, 2012, 7209 : 331 - 338
12345