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 条
  • [21] Lagrangian heuristics for the Linear Ordering Problem
    Belloni, A
    Lucena, A
    METAHEURISTICS: COMPUTER DECISION-MAKING, 2004, 86 : 37 - 63
  • [22] ON THE LINEAR ORDERING PROBLEM AND THE RANKABILITY OF DATA
    Cameron, Thomas R.
    Charmot, Sebastian
    Pulaj, Jonad
    FOUNDATIONS OF DATA SCIENCE, 2021, 3 (02): : 133 - 149
  • [23] Journey to the Center of the Linear Ordering Problem
    Hernando, Leticia
    Mendiburu, Alexander
    Lozano, Jose A.
    GECCO'20: PROCEEDINGS OF THE 2020 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2020, : 201 - 209
  • [24] Primal Heuristic for the Linear Ordering Problem
    Agrawal, Ravi
    Iranmanesh, Ehsan
    Krishnamurti, Ramesh
    ICORES: PROCEEDINGS OF THE 8TH INTERNATIONAL CONFERENCE ON OPERATIONS RESEARCH AND ENTERPRISE SYSTEMS, 2019, : 151 - 156
  • [25] From Weighted to Unweighted Model Counting
    Chakraborty, Supratik
    Fried, Dror
    Meel, Kuldeep S.
    Vardi, Moshe Y.
    PROCEEDINGS OF THE TWENTY-FOURTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI), 2015, : 689 - 695
  • [26] A diversity-aware memetic algorithm for the linear ordering Problem
    Lázaro Lugo
    Carlos Segura
    Gara Miranda
    Memetic Computing, 2022, 14 : 395 - 409
  • [27] A diversity-aware memetic algorithm for the linear ordering Problem
    Lugo, Lazaro
    Segura, Carlos
    Miranda, Gara
    MEMETIC COMPUTING, 2022, 14 (04) : 395 - 409
  • [28] On the Complexity of a Linear Ordering of Weighted Directed Acyclic Graphs
    Shchekalev, M. I.
    Bokov, G. V.
    Kudryavtsev, V. B.
    MOSCOW UNIVERSITY MATHEMATICS BULLETIN, 2021, 76 (01) : 35 - 36
  • [29] On the Complexity of a Linear Ordering of Weighted Directed Acyclic Graphs
    M. I. Shchekalev
    G. V. Bokov
    V. B. Kudryavtsev
    Moscow University Mathematics Bulletin, 2021, 76 : 35 - 36
  • [30] Multirobot Forest Coverage for Weighted and Unweighted Terrain
    Zheng, Xiaoming
    Koenig, Sven
    Kempe, David
    Jain, Sonal
    IEEE TRANSACTIONS ON ROBOTICS, 2010, 26 (06) : 1018 - 1031
12345