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.
| Original language | English |
|---|---|
| Pages (from-to) | 107-158 |
| Number of pages | 52 |
| Journal | Annals of Operations Research |
| Volume | 175 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 1 Feb 2010 |
Keywords
- Acyclic subgraph
- Aggregation of preferences
- Combinatorial optimization
- Combinatorics
- 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