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

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

Authors: Irène Charon, Olivier Hudry 

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

Recommendations

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

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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 Combinatorial Proof of a Conjecture of Goldberg and Moon
• A Cutting Plane Algorithm for the Linear Ordering Problem
• A NEW MEASURE OF RANK CORRELATION
• 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 for the linear ordering problem with cumulative costs
• A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments
• A coarseness conjecture of Erdös
• A comparison of Dodgson's method and Kemeny's rule
• 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 note on the number of Hamiltonian paths in strong tournaments
• A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
• A survey on the complexity of tournament solutions
• A survey on the linear ordering problem for weighted or unweighted tournaments
• A tournament of order 14 with disjoint Banks and Slater sets
• 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
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• 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
• Compositions of Graphs and Polyhedra IV: Acyclic Spanning Subgraphs
• Computational Experience with an Interior Point Cutting Plane Algorithm
• Condorcet Social Choice Functions
• Constructive Quasi-Ramsey Numbers and Tournament Ranking
• Context-independent scatter and tabu search for permutation problems
• 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
• Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
• Discriminant Functions and Majority Voting
• Divide-and-conquer approximation algorithms via spreading metrics
• Efficient local search algorithms for the linear ordering problem
• Exact algorithms for the quadratic linear ordering problem
• 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
• Finite ordered sets. Concepts, results and applications
• 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
• 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 distance between Slater orders and Copeland orders of tournaments
• 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
• NP-hardness results for the aggregation of linear orders into median orders
• New Approximation Techniques for Some Linear Ordering Problems
• 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 Sets of Arcs Containing No Cycles in a Tournament*
• On Sets of Consistent Arcs in a Tournament
• On non-\(\{0,{1\over 2},1\}\) extreme points of the generalized transitive tournament polytope
• On the Minimum Violations Ranking of a Tournament
• On the complexity of Slater's problems
• 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
• Optimal Weighted Ancestry Relationships
• Optimal ranking of tournaments
• 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 Tournaments
• 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
• Rankings from Paired Comparisons
• Revised GRASP with path-relinking for the linear ordering problem
• SERIATION USING ASYMMETRIC PROXIMITY MEASURES
• Self-tuning of the noising methods
• 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 TREATMENT OF TIES IN RANKING PROBLEMS
• The Dodgson ranking and its relation to Kemeny's method and Slater's rule
• The Maximum Order of the Group of a Tournament
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• The Voting Problem
• The biorder polytope
• The bipartisan set of a tournament game
• The complexity of Kemeny elections
• The complexity of computing medians of relations.
• 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 median procedure in cluster analysis and social choice theory
• 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 traveling salesman problem on a graph and some related integer polyhedra
• 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 in the Medieval Papacy and Religious Orders
• Voting schemes for which it can be difficult to tell who won the election
• Zwei Algorithmen zur Lösung eines komplexen Reihenfolgeproblems

Cited In (28)

• Strong Condorcet criterion for the linear ordering problem
• 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
• A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments
• 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
• 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
• A survey on the linear ordering problem for weighted or unweighted tournaments
• Complexity results for extensions of median orders to different types of remoteness
• Global approaches for facility layout and VLSI floorplanning
• 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
• Randomized algorithms for lexicographic inference
• 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

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)