On the hardness of maximum rank aggregation problems

DOI10.1016/J.JDA.2014.10.002MaRDI QIDQ2018536zbMATHOpenAlexFDO

Authors Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Andreas Hofmeier

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) Individual preferences (91B08) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On maximum rank aggregation problems
• A generalization of the assignment problem, and its application to the rank aggregation problem
• An efficient approach for the rank aggregation problem
• Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
• On the complexity of the generalized MinRank problem
• On the complexity of ranking
• Classified rank-maximal matchings and popular matchings -- algorithms and hardness
• An algorithm for rank aggregation problem

Cites work

• scientific article; zbMATH DE number 5485441 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3584785 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Computer Method for Calculating Kendall's Tau with Ungrouped Data
• Aggregating inconsistent information: ranking and clustering
• Aggregation of partial rankings, \(p\)-ratings and top-\(m\) lists
• Algorithms on Strings, Trees and Sequences
• Combinatorics of genome rearrangements.
• Comparing Partial Rankings
• Comparing Top k Lists
• Comparing and aggregating partial orders with Kendall tau distances
• Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Fixed-parameter algorithms for Kemeny rankings
• Fundamentals of parameterized complexity
• Metric methods for analyzing partially ranked data
• Metrics on permutations, a survey
• Multiple genome rearrangement by swaps and by element duplications
• On covering problems of codes
• On maximum rank aggregation problems
• On the complexity of crossings in permutations
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Swap and mismatch edit distance
• The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders
• Voting schemes for which it can be difficult to tell who won the election

Cited in

(12)

• Aggregating preferences represented by conditional preference networks
• Sorting of decision-making methods based on their outcomes using dominance-vector hesitant fuzzy-based distance
• On the complexity of crossings in permutations
• Ranking chain sum orders
• A note on permutations and rank aggregation
• Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
• On maximum rank aggregation problems
• NP-hardness results for the aggregation of linear orders into median orders
• The complexity landscape of outcome determination in judgment aggregation
• Rank aggregation in cyclic sequences
• An efficient approach for the rank aggregation problem
• On the complexity of ``Superdetermined minrank instances

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2018536)