On the hardness of maximum rank aggregation problems

DOI10.1016/j.jda.2014.10.002zbMath1322.68086OpenAlexW2087399592MaRDI QIDQ2018536

Christian Bachmaier, Andreas Gleißner, Andreas Hofmeier, Franz-Josef Brandenburg

Publication date: 24 March 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2014.10.002

zbMATH Keywords

computational complexityrank aggregationFPTcenter consensusmaximum rankingpermutation metrics

Mathematics Subject Classification ID

Decision theory (91B06) Combinatorics in computer science (68R05) Individual preferences (91B08) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Ranking chain sum orders ⋮ Aggregating preferences represented by conditional preference networks ⋮ The Complexity Landscape of Outcome Determination in Judgment Aggregation ⋮ Sorting of decision-making methods based on their outcomes using dominance-vector hesitant fuzzy-based distance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• On covering problems of codes
• On the complexity of crossings in permutations
• Fixed-parameter algorithms for Kemeny rankings
• Metric methods for analyzing partially ranked data
• Voting schemes for which it can be difficult to tell who won the election
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Swap and mismatch edit distance
• Aggregation of partial rankings, \(p\)-ratings and top-\(m\) lists
• The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders
• Multiple genome rearrangement by swaps and by element duplications
• COMPARING AND AGGREGATING PARTIAL ORDERS WITH KENDALL TAU DISTANCES
• On Maximum Rank Aggregation Problems
• Sorting by Transpositions Is Difficult
• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
• Algorithms on Strings, Trees and Sequences
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Comparing Top k Lists
• A Computer Method for Calculating Kendall's Tau with Ungrouped Data
• Comparing Partial Rankings
• Aggregating inconsistent information

This page was built for publication: On the hardness of maximum rank aggregation problems