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 条
  • [1] A survey on the linear ordering problem for weighted or unweighted tournaments
    Irène Charon
    Olivier Hudry
    4OR, 2007, 5 : 5 - 60
  • [2] An updated survey on the linear ordering problem for weighted or unweighted tournaments
    Irène Charon
    Olivier Hudry
    Annals of Operations Research, 2010, 175 : 107 - 158
  • [3] An updated survey on the linear ordering problem for weighted or unweighted tournaments
    Charon, Irene
    Hudry, Olivier
    ANNALS OF OPERATIONS RESEARCH, 2010, 175 (01) : 107 - 158
  • [4] A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments
    Charon, Irene
    Hudry, Olivier
    DISCRETE APPLIED MATHEMATICS, 2006, 154 (15) : 2097 - 2116
  • [5] A linear ordering problem with weighted rank
    Manuel V. C. Vieira
    Journal of Combinatorial Optimization, 2024, 47
  • [6] A linear ordering problem with weighted rank
    Vieira, Manuel V. C.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2024, 47 (02)
  • [7] Ordering by Weighted Number of Wins Gives a Good Ranking for Weighted Tournaments
    Coppersmith, Don
    Fleischer, Lisa K.
    Rurda, Atri
    ACM TRANSACTIONS ON ALGORITHMS, 2010, 6 (03)
  • [8] Descent with Mutations Applied to the Linear Ordering Problem
    Hudry, Olivier
    COMBINATORIAL OPTIMIZATION, ISCO 2018, 2018, 10856 : 253 - 264
  • [9] GENETIC ALGORITHMS FOR THE LINEAR ORDERING PROBLEM
    Kroemer, Pavel
    Snasel, Vaclav
    Platos, Jan
    Husek, Dusan
    NEURAL NETWORK WORLD, 2009, 19 (01) : 65 - 80
  • [10] Understanding Instance Complexity in the Linear Ordering Problem
    Ceberio, Josu
    Hernando, Leticia
    Mendiburu, Alexander
    Lozano, Jose A.
    INTELLIGENT DATA ENGINEERING AND AUTOMATED LEARNING - IDEAL 2013, 2013, 8206 : 479 - 486
12345