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

DOI10.1007/S10288-007-0036-6MaRDI QIDQ2644372zbMATH OpenOpenAlexFDO

Authors Irène Charon, Olivier Hudry

Publication date 31 August 2007

Published in 4OR (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10288-007-0036-6

zbMATH Keywords

acyclic subgraphaggregation of preferencescombinatorial optimizationcombinatoricscomplexityfeedback arc setgraph theoryKemeny's problemlinear ordering problemmedian orderoptimal triangulationreversing setSlater's problemsocial choicetournament solutionsvoting theory

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Applications of graph theory (05C90) Total orders (06A05) Combinatorics of partially ordered sets (06A07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Integer programming (90C10) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59)

Review text

A relation \(R\) defined on a finite set \(X\) of \(n\) elements (that may represent different teams or alternatives, for example) is a preference relation if for each pair of distinct elements \(u\) and \(v\) either \(uRv\) or \(vRu\), but not both. Let there be given a collection \(P\) of \(m\) preference relations on the same set \(X\). The general linear ordering problem is to determine a single linear order \(O\) with the property that the total number of disagreements between \(O\) and the preferences in \(P\) is minimized. (There may or may not be weights associated with the preferences to be taken into account.) The authors survey work done on various formulations of this and related problems, both when \(m=1\) and in general. In particular, they present complexity results and bounds and discuss various algorithms that have been developed for treating these problems.

Recommendations

• An updated survey on the linear ordering problem for weighted or unweighted tournaments
• A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments
• Strong Condorcet criterion for the linear ordering problem
• Publication:4730974
• scientific article; zbMATH DE number 1855678

Cites work

• 0, 1/2‐Cuts and the Linear Ordering Problem: Surfaces That Define Facets
• A 16-vertex tournament for which Banks set and Slater set are disjoint
• A branch and bound algorithm for maximum likelihood paired comparison ranking
• A branch and bound algorithm for the acyclic subgraph problem
• A branch search algorithm for maximum likelihood paired comparison ranking
• A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments
• A coarseness conjecture of Erdös
• A Combinatorial Proof of a Conjecture of Goldberg and Moon
• A Cutting Plane Algorithm for the Linear Ordering Problem
• A fast and effective heuristic for the feedback arc set problem
• A new algorithm for ranking players of a round-robin tournament
• A new heuristic algorithm solving the linear ordering problem
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• A note on ``Bank winners in tournaments are difficult to recognize by G. J. Woeginger
• A note on small linear-ordering polytopes
• A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
• Aggregating inconsistent information
• Algorithmic aspects of using small instance relaxations in parallel branch-and-cut
• An algorithmic view of voting
• An experimental evaluation of a scatter search for the linear ordering problem
• Approximating minimum feedback sets and multicuts in directed graphs
• Approximations for the maximum acyclic subgraph problem
• Approximative Algorithms for Discrete Optimization Problems
• Banks winners in tournaments are difficult to recognize
• Branch cuts in strongly connected graphs and permutation potentials
• Combinatorial optimization and small polytopes
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Comparing the efficacy of ranking methods for multiple round-robin tournaments
• Condorcet Social Choice Functions
• Constructive Quasi-Ramsey Numbers and Tournament Ranking
• Counterexamples to Adám's conjecture on arc reversals in directed graphs
• Covering relations, closest orderings and Hamiltonian bypaths in tournaments
• Covering sets and a new Condorcet choice correspondence
• Cycles of Each Length in Regular Tournaments
• Cyclic tournaments and cooperative majority voting: A solution
• Determining the automorphism group of the linear ordering polytope
• Discriminant Functions and Majority Voting
• Exact and heuristic algorithms for the weighted feedback arc set problem: A special case of the skew-symmetric quadratic assignment problem
• Facets of linear signed order polytopes.
• Facets of the linear ordering polytope
• Facets of the linear ordering polytope: a unification for the fence family through weighted graphs
• Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
• Graphs with forbidden subgraphs
• Handbook of metaheuristics
• Hardness of fully dense problems
• How to recycle your facets
• scientific article; zbMATH DE number 3833066 (Why is no real title available?)
• scientific article; zbMATH DE number 3642532 (Why is no real title available?)
• scientific article; zbMATH DE number 432770 (Why is no real title available?)
• scientific article; zbMATH DE number 6118220 (Why is no real title available?)
• scientific article; zbMATH DE number 3888925 (Why is no real title available?)
• scientific article; zbMATH DE number 3148878 (Why is no real title available?)
• scientific article; zbMATH DE number 3850790 (Why is no real title available?)
• scientific article; zbMATH DE number 3880741 (Why is no real title available?)
• scientific article; zbMATH DE number 3902051 (Why is no real title available?)
• scientific article; zbMATH DE number 3902379 (Why is no real title available?)
• scientific article; zbMATH DE number 3980481 (Why is no real title available?)
• scientific article; zbMATH DE number 140117 (Why is no real title available?)
• scientific article; zbMATH DE number 3472085 (Why is no real title available?)
• scientific article; zbMATH DE number 3492710 (Why is no real title available?)
• scientific article; zbMATH DE number 3632478 (Why is no real title available?)
• scientific article; zbMATH DE number 3633982 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1288298 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1022238 (Why is no real title available?)
• scientific article; zbMATH DE number 1022239 (Why is no real title available?)
• scientific article; zbMATH DE number 1163867 (Why is no real title available?)
• scientific article; zbMATH DE number 1962001 (Why is no real title available?)
• scientific article; zbMATH DE number 2013555 (Why is no real title available?)
• scientific article; zbMATH DE number 1489805 (Why is no real title available?)
• scientific article; zbMATH DE number 194544 (Why is no real title available?)
• scientific article; zbMATH DE number 3013308 (Why is no real title available?)
• scientific article; zbMATH DE number 825126 (Why is no real title available?)
• scientific article; zbMATH DE number 878679 (Why is no real title available?)
• scientific article; zbMATH DE number 892279 (Why is no real title available?)
• scientific article; zbMATH DE number 1422720 (Why is no real title available?)
• scientific article; zbMATH DE number 3221981 (Why is no real title available?)
• scientific article; zbMATH DE number 3303831 (Why is no real title available?)
• scientific article; zbMATH DE number 3304772 (Why is no real title available?)
• scientific article; zbMATH DE number 3329639 (Why is no real title available?)
• scientific article; zbMATH DE number 3378948 (Why is no real title available?)
• Implementation analysis of efficient heuristic algorithms for the traveling salesman problem
• Induced binary probabilities and the linear ordering polytope: A status report
• Intensification and diversification with elite tabu search solutions for the linear ordering problem
• Lamarckian genetic algorithms applied to the aggregation of preferences
• Links between the Slater index and the Ryser index of tournaments
• Majority Decisions and Transitivity: Some Special Cases
• Majority Rule Under Transitivity Constraints
• Matrix multiplication via arithmetic progressions
• Maximum likelihood paired comparison ranking by linear programming
• Maximum likelihood paired-comparison ranking and quadratic assignment
• Maximum-likelihood paired comparison rankings
• Measuring intransitivity
• Median linear orders: Heuristics and a branch and bound algorithm
• Metaheuristics for Hard Optimization
• More facets from fences for linear ordering and acyclic subgraph polytopes
• New Facets of the Linear Ordering Polytope
• New results on the computation of median orders
• Note—A Note on Majority Rule under Transitivity Constraints
• On non-\(\{0,{1\over 2},1\}\) extreme points of the generalized transitive tournament polytope
• On Sets of Arcs Containing No Cycles in a Tournament*
• On Sets of Consistent Arcs in a Tournament
• On the acyclic subgraph polytope
• On the integral dicycle packings and covers and the linear ordering polytope
• On the maximal order of cyclicity of antisymmetric directed graphs
• On the maximum cardinality of a consistent set of arcs in a random tournament
• On the maximum number of Hamiltonian paths in tournaments
• On the Minimum Violations Ranking of a Tournament
• Optimal ranking of tournaments
• Optimal Weighted Ancestry Relationships
• Optimization, approximation, and complexity classes
• Ordering by weighted number of wins gives a good ranking for weighted tournaments
• Packing directed circuits fractionally
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Random generation of tournaments and asymmetric graphs with given out-degrees
• Random utility representation of binary choice probabilities: Critical graphs yielding critical necessary conditions
• Ranking in Tournaments and Group Decisionmaking
• Ranking players in multiple tournaments
• Ranking the Participants in a Tournament
• Ranking the Vertices of a Paired Comparison Digraph
• Ranking Tournaments
• Rankings from Paired Comparisons
• SERIATION USING ASYMMETRIC PROXIMITY MEASURES
• Slater orders and Hamiltonian paths of tournaments
• Slater's winners of a tournament may not be in the Banks set
• Solving real-world linear ordering problems using a primal-dual interior point cutting plane method
• Some Equivalence Classes in Paired Comparisons
• Sophisticated voting outcomes and agenda control
• Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments
• The biorder polytope
• The bipartisan set of a tournament game
• The complexity of computing medians of relations.
• The Dodgson ranking and its relation to Kemeny's method and Slater's rule
• The linear ordering problem with cumulative costs
• The linear ordering problem: instances, search space analysis and algorithms
• The maximum number of Hamiltonian paths in tournaments
• The Maximum Order of the Group of a Tournament
• The median procedure in cluster analysis and social choice theory
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• The noising methods: A generalization of some metaheuristics
• The noising methods: A survey
• The omnipresence of Lagrange
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The reversing number of a digraph
• THE TREATMENT OF TIES IN RANKING PROBLEMS
• The Voting Problem
• Tight Bounds for the Maximum Acyclic Subgraph Problem
• Tournament Ranking with Expected Profit in Polynomial Time
• Tournament solutions and majority voting
• Tournaments as feedback arc sets
• Un algorithme pour pallier l'effet Condorcet
• Upsets in round robin tournaments
• Upsets in Round Robin Tournaments
• Variable neighborhood search for the linear ordering problem
• Voting schemes for which it can be difficult to tell who won the election
• Zwei Algorithmen zur Lösung eines komplexen Reihenfolgeproblems

Cited in

(30)

• A survey on the complexity of tournament solutions
• Testing probabilistic models of choice using column generation
• Monotonicity-based consensus states for the monometric rationalisation of ranking rules and how they are affected by ties
• Surveys in operations research
• Weighted majority tournaments and Kemeny ranking with 2-dimensional Euclidean preferences
• A linear ordering problem of sets
• Fixed-parameter tractability results for feedback set problems in tournaments
• NP-hardness results for the aggregation of linear orders into median orders
• Distance and consensus for preference relations corresponding to ordered partitions
• A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments
• The linear ordering problem revisited
• Twelve surveys in operations research
• Efficient local search algorithms for the linear ordering problem
• Self-tuning of the noising methods
• Improved parameterized algorithms for the Kemeny aggregation problem
• A benchmark library and a comparison of heuristic methods for the linear ordering problem
• scientific article; zbMATH DE number 1855678 (Why is no real title available?)
• Strong Condorcet criterion for the linear ordering problem
• Randomized algorithms for lexicographic inference
• Voting procedures, complexity of
• Rank aggregation in cyclic sequences
• A parameterized algorithm for subset feedback vertex set in tournaments
• A linear ordering problem with weighted rank
• Query complexity of tournament solutions
• Kernels for feedback arc set in tournaments
• Still more surveys in operations research\dots
• Width notions for ordering-related problems
• Computing the minimal covering set
• A tournament of order 14 with disjoint Banks and Slater sets
• An updated survey on the linear ordering problem for weighted or unweighted tournaments

Describes a project that uses

Uses Software

• PORTA
• LOLIB
• RAMP

This page was built for publication: A survey on the linear ordering problem for weighted or unweighted tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2644372)