An updated survey on the linear ordering problem for weighted or unweighted tournaments

DOI10.1007/s10479-009-0648-7zbMath1185.90197OpenAlexW1972789308MaRDI QIDQ970187

Olivier Hudry, Irène Charon

Publication date: 10 May 2010

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-009-0648-7

zbMATH Keywords

combinatoricscomplexitycombinatorial optimizationvoting theorygraph theorysocial choiceacyclic subgraphfeedback arc setmedian orderoptimal triangulationlinear ordering problemaggregation of preferencestournament solutionsKemeny's problemreversing setSlater's problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Voting theory (91B12) Social choice (91B14)

Related Items (23)

Robust Learning of Consumer Preferences ⋮ Decomposability index of tournaments ⋮ A linear ordering problem of sets ⋮ Scheduling interrelated activities in complex projects under high-order rework: a DSM-based approach ⋮ Monotonicity-based consensus states for the monometric rationalisation of ranking rules and how they are affected by ties ⋮ Rankability and linear ordering problem: probabilistic insight and algorithms ⋮ A linear ordering problem with weighted rank ⋮ Adjacencies on random ordering polytopes and flow polytopes ⋮ Maximum distance between Slater orders and Copeland orders of tournaments ⋮ On the computation of median linear orders, of median complete preorders and of median weak orders ⋮ Randomized Algorithms for Lexicographic Inference ⋮ Surprises in Knockout Tournaments ⋮ Evidential reasoning in large partially ordered sets. Application to multi-label classification, ensemble clustering and preference aggregation ⋮ A new consensus ranking approach for correlated ordinal information based on Mahalanobis distance ⋮ Global Approaches for Facility Layout and VLSI Floorplanning ⋮ Block-insertion-based algorithms for the linear ordering problem ⋮ Linear time algorithms to solve the linear ordering problem for oriented tree based graphs ⋮ Beyond pairwise comparisons in social choice: a setwise Kemeny aggregation problem ⋮ On the complexity of Slater's problems ⋮ Probabilistic transitivity in sports ⋮ Bayesian inference and model comparison for random choice structures ⋮ Bounds on the disparity and separation of tournament solutions ⋮ Complexity results for extensions of median orders to different types of remoteness

Uses Software

• PORTA
• LOLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Revised GRASP with path-relinking for the linear ordering problem
• Median linear orders: Heuristics and a branch and bound algorithm
• Maximum distance between Slater orders and Copeland orders of tournaments
• A fast and effective heuristic for the feedback arc set problem
• On the maximum cardinality of a consistent set of arcs in a random tournament
• Slater's winners of a tournament may not be in the Banks set
• Covering relations, closest orderings and Hamiltonian bypaths in tournaments
• A note on the number of Hamiltonian paths in strong tournaments
• The complexity of Kemeny elections
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Cyclic tournaments and cooperative majority voting: A solution
• Matrix multiplication via arithmetic progressions
• A tournament of order 14 with disjoint Banks and Slater sets
• A survey on the complexity of tournament solutions
• On the complexity of Slater's problems
• Upsets in round robin tournaments
• A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
• Sophisticated voting outcomes and agenda control
• Counterexamples to Adám's conjecture on arc reversals in directed graphs
• Covering sets and a new Condorcet choice correspondence
• Voting schemes for which it can be difficult to tell who won the election
• A branch and bound algorithm for the acyclic subgraph problem
• The median procedure in cluster analysis and social choice theory
• Induced binary probabilities and the linear ordering polytope: A status report
• Optimization, approximation, and complexity classes
• The bipartisan set of a tournament game
• On the maximal order of cyclicity of antisymmetric directed graphs
• Measuring intransitivity
• Random generation of tournaments and asymmetric graphs with given out-degrees
• Intensification and diversification with elite tabu search solutions for the linear ordering problem
• More facets from fences for linear ordering and acyclic subgraph polytopes
• Approximations for the maximum acyclic subgraph problem
• A new algorithm for ranking players of a round-robin tournament
• New results on the computation of median orders
• Tournament solutions and majority voting
• A 16-vertex tournament for which Banks set and Slater set are disjoint
• Approximating minimum feedback sets and multicuts in directed graphs
• Lamarckian genetic algorithms applied to the aggregation of preferences
• Links between the Slater index and the Ryser index of tournaments
• Facets of linear signed order polytopes.
• Comparing the efficacy of ranking methods for multiple round-robin tournaments
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• The biorder polytope
• The Dodgson ranking and its relation to Kemeny's method and Slater's rule
• A note on ``Bank winners in tournaments are difficult to recognize by G. J. Woeginger
• The linear ordering problem: instances, search space analysis and algorithms
• Combinatorial optimization and small polytopes
• A new heuristic algorithm solving the linear ordering problem
• An experimental evaluation of a scatter search for the linear ordering problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The reversing number of a digraph
• On the integral dicycle packings and covers and the linear ordering polytope
• Packing directed circuits fractionally
• Random utility representation of binary choice probabilities: Critical graphs yielding critical necessary conditions
• Tournaments as feedback arc sets
• On non-\(\{0,{1\over 2},1\}\) extreme points of the generalized transitive tournament polytope
• Solving real-world linear ordering problems using a primal-dual interior point cutting plane method
• NP-hardness results for the aggregation of linear orders into median orders
• The maximum number of Hamiltonian paths in tournaments
• A note on small linear-ordering polytopes
• A comparison of Dodgson's method and Kemeny's rule
• A branch-and-bound algorithm for the linear ordering problem with cumulative costs
• A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments
• The linear ordering problem with cumulative costs
• Variable neighborhood search for the linear ordering problem
• Facets of the linear ordering polytope: a unification for the fence family through weighted graphs
• How to recycle your facets
• Graphs with forbidden subgraphs
• Branch cuts in strongly connected graphs and permutation potentials
• Ranking players in multiple tournaments
• Banks winners in tournaments are difficult to recognize
• Implementation analysis of efficient heuristic algorithms for the traveling salesman problem
• Finite ordered sets. Concepts, results and applications
• Hardness of fully dense problems
• A survey on the linear ordering problem for weighted or unweighted tournaments
• On the maximum number of Hamiltonian paths in tournaments
• An Algorithmic View of Voting
• Context-Independent Scatter and Tabu Search for Permutation Problems
• Exact Algorithms for the Quadratic Linear Ordering Problem
• Divide-and-conquer approximation algorithms via spreading metrics
• Efficient local search algorithms for the linear ordering problem
• Exact and heuristic algorithms for the weighted feedback arc set problem: A special case of the skew-symmetric quadratic assignment problem
• Ranking in Tournaments and Group Decisionmaking
• A Cutting Plane Algorithm for the Linear Ordering Problem
• The Voting Problem
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
• Voting in the Medieval Papacy and Religious Orders
• Self-tuning of the noising methods
• The traveling salesman problem on a graph and some related integer polyhedra
• Ranking the Vertices of a Paired Comparison Digraph
• Facets of the linear ordering polytope
• On the Minimum Violations Ranking of a Tournament
• Tournament Ranking with Expected Profit in Polynomial Time
• Ranking the Participants in a Tournament
• A branch search algorithm for maximum likelihood paired comparison ranking
• Optimal Weighted Ancestry Relationships
• Discriminant Functions and Majority Voting
• Maximum likelihood paired-comparison ranking and quadratic assignment
• SERIATION USING ASYMMETRIC PROXIMITY MEASURES
• Majority Decisions and Transitivity: Some Special Cases
• Un algorithme pour pallier l'effet Condorcet
• Note—A Note on Majority Rule under Transitivity Constraints
• Condorcet Social Choice Functions
• Approximative Algorithms for Discrete Optimization Problems
• Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments
• Constructive Quasi-Ramsey Numbers and Tournament Ranking
• Compositions of Graphs and Polyhedra IV: Acyclic Spanning Subgraphs
• Tight Bounds for the Maximum Acyclic Subgraph Problem
• Computational Experience with an Interior Point Cutting Plane Algorithm
• New Approximation Techniques for Some Linear Ordering Problems
• New Facets of the Linear Ordering Polytope
• Majority Rule Under Transitivity Constraints
• Metaheuristics for Hard Optimization
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• 0, 1/2‐Cuts and the Linear Ordering Problem: Surfaces That Define Facets
• Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
• Ranking Tournaments
• Upsets in Round Robin Tournaments
• On Sets of Consistent Arcs in a Tournament
• Rankings from Paired Comparisons
• Maximum-likelihood paired comparison rankings
• Cycles of Each Length in Regular Tournaments
• A coarseness conjecture of Erdös
• Zwei Algorithmen zur Lösung eines komplexen Reihenfolgeproblems
• Some Equivalence Classes in Paired Comparisons
• A Combinatorial Proof of a Conjecture of Goldberg and Moon
• On Sets of Arcs Containing No Cycles in a Tournament*
• Maximum likelihood paired comparison ranking by linear programming
• The Maximum Order of the Group of a Tournament
• Optimal ranking of tournaments
• A branch and bound algorithm for maximum likelihood paired comparison ranking
• A NEW MEASURE OF RANK CORRELATION
• THE TREATMENT OF TIES IN RANKING PROBLEMS
• Aggregating inconsistent information
• Ordering by weighted number of wins gives a good ranking for weighted tournaments
• The omnipresence of Lagrange
• Handbook of metaheuristics
• Algorithmic aspects of using small instance relaxations in parallel branch-and-cut
• Determining the automorphism group of the linear ordering polytope
• The noising methods: A generalization of some metaheuristics

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