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

DOI10.1007/S10479-009-0648-7zbMATH Open1185.90197OpenAlexW1972789308MaRDI QIDQ970187FDOQ970187

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

combinatorial optimizationcombinatoricsgraph theorycomplexityfeedback arc setsocial choicevoting theorymedian orderlinear ordering problemoptimal triangulationacyclic subgraphaggregation of preferencestournament solutionsKemeny's problemreversing setSlater's problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (25)

• Global Approaches for Facility Layout and VLSI Floorplanning
• Evidential reasoning in large partially ordered sets. Application to multi-label classification, ensemble clustering and preference aggregation
• Surprises in Knockout Tournaments
• Rankability and linear ordering problem: probabilistic insight and algorithms
• Probabilistic transitivity in sports
• 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
• Decomposability index of tournaments
• On the complexity of Slater's problems
• A linear ordering problem of sets
• On the computation of median linear orders, of median complete preorders and of median weak orders
• Weighted majority tournaments and Kemeny ranking with 2-dimensional Euclidean preferences
• Randomized Algorithms for Lexicographic Inference
• Bayesian inference and model comparison for random choice structures
• Scheduling interrelated activities in complex projects under high-order rework: a DSM-based approach
• Maximum distance between Slater orders and Copeland orders of tournaments
• Block-insertion-based algorithms for the linear ordering problem
• Complexity results for extensions of median orders to different types of remoteness
• Title not available (Why is that?)
• Monotonicity-based consensus states for the monometric rationalisation of ranking rules and how they are affected by ties
• A linear ordering problem with weighted rank
• A new consensus ranking approach for correlated ordinal information based on Mahalanobis distance
• Robust Learning of Consumer Preferences
• Bounds on the disparity and separation of tournament solutions
• Adjacencies on random ordering polytopes and flow polytopes

Uses Software

• PORTA
• LOLIB

   Recommendations

• A survey on the linear ordering problem for weighted or unweighted tournaments 👍 👎
• Title not available (Why is that?) 👍 👎
• A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: An updated 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 Q970187)