Complexity results for extensions of median orders to different types of remoteness

DOI10.1007/s10479-013-1342-3zbMath1320.91057OpenAlexW1978225558MaRDI QIDQ2348767

Olivier Hudry

Publication date: 15 June 2015

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

Full work available at URL: https://doi.org/10.1007/s10479-013-1342-3

zbMATH Keywords

complexityNP-completenesstournamentcomplete preorderbinary relationslinear orderweak orderremotenessmedian orderaggregation of preferencessymmetric difference distanceKemeny's problemSlater's problemmedian relation

Mathematics Subject Classification ID

Voting theory (91B12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Social choice (91B14)

Related Items (max. 100)

Voting Procedures, Complexity of ⋮ Primary facets of order polytopes

Cites Work

• On the computation of median linear orders, of median complete preorders and of median weak orders
• The complexity of Kemeny elections
• Evaluation and decision models with multiple criteria. Stepping stones for the analyst.
• An updated survey on the linear ordering problem for weighted or unweighted tournaments
• A survey on the complexity of tournament solutions
• On the complexity of Slater's problems
• Voting schemes for which it can be difficult to tell who won the election
• The median procedure in cluster analysis and social choice theory
• NP-hardness results for the aggregation of linear orders into median orders
• Consensus theories. An oriented survey
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Ranking Tournaments
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity results for extensions of median orders to different types of remoteness