A survey on the linear ordering problem for weighted or unweighted tournaments

Irène Charon; Olivier Hudry

doi:10.1007/s10288-007-0036-6

A survey on the linear ordering problem for weighted or unweighted tournaments

Irène Charon
, Olivier Hudry

Telecom Paris

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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.

langue originale	Anglais
Pages (de - à)	5-60
Nombre de pages	56
journal	4OR
Volume	5
Numéro de publication	1
Les DOIs	https://doi.org/10.1007/s10288-007-0036-6
état	Publié - 1 janv. 2007

Accès au document

10.1007/s10288-007-0036-6

Contient cette citation

@article{34bf7ea5aa504de7973c0fca9a9ad668,

title = "A survey on the linear ordering problem for weighted or unweighted tournaments",

abstract = "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.",

keywords = "Acyclic subgraph, Aggregation of preferences, Complexity, Feedback arc set, Graph theory, Kemeny's problem, Linear ordering problem, Median order, Optimal triangulation, Reversing set, Slater's problem, Social choice, Tournament solutions, Voting theory",

author = "Ir{\`e}ne Charon and Olivier Hudry",

year = "2007",

month = jan,

day = "1",

doi = "10.1007/s10288-007-0036-6",

language = "English",

volume = "5",

pages = "5--60",

journal = "4OR",

issn = "1619-4500",

number = "1",

}

TY - JOUR

T1 - A survey on the linear ordering problem for weighted or unweighted tournaments

AU - Charon, Irène

AU - Hudry, Olivier

PY - 2007/1/1

Y1 - 2007/1/1

N2 - 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.

AB - 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.

KW - Acyclic subgraph

KW - Aggregation of preferences

KW - Complexity

KW - Feedback arc set

KW - Graph theory

KW - Kemeny's problem

KW - Linear ordering problem

KW - Median order

KW - Optimal triangulation

KW - Reversing set

KW - Slater's problem

KW - Social choice

KW - Tournament solutions

KW - Voting theory

U2 - 10.1007/s10288-007-0036-6

DO - 10.1007/s10288-007-0036-6

M3 - Article

AN - SCOPUS:33947670530

SN - 1619-4500

VL - 5

SP - 5

EP - 60

JO - 4OR

JF - 4OR

IS - 1

ER -

A survey on the linear ordering problem for weighted or unweighted tournaments

Résumé

Accès au document

Empreinte digitale

Contient cette citation