Fixed-parameter algorithms for Kemeny rankings

DOI10.1016/j.tcs.2009.08.033zbMath1179.91062OpenAlexW2162918886WikidataQ57359797 ScholiaQ57359797MaRDI QIDQ1035688

Rolf Niedermeier, Nadja Betzler, Frances A. Rosamond, Michael R. Fellows, Jiong Guo

Publication date: 4 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.08.033

zbMATH Keywords

winner determinationfixed-parameter tractabilitycomputational social choicerank aggregationvoting systemsconsensus finding

Mathematics Subject Classification ID

Voting theory (91B12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (21)

Ranking chain sum orders ⋮ Studies in Computational Aspects of Voting ⋮ Space reduction constraints for the median of permutations problem ⋮ A unifying rank aggregation framework to suitably and efficiently aggregate any kind of rankings ⋮ Recognizing when a preference system is close to admitting a master list ⋮ On weakly and strongly popular rankings ⋮ Recognizing when a preference system is close to admitting a master list ⋮ Kernelization complexity of possible winner and coalitional manipulation problems in voting ⋮ Computing kemeny rankings from \(d\)-Euclidean preferences ⋮ Experiments with Kemeny ranking: What works when? ⋮ Towards a dichotomy for the possible winner problem in elections based on scoring rules ⋮ Parameterizing by the number of numbers ⋮ Parameterized computational complexity of Dodgson and Young elections ⋮ On the hardness of maximum rank aggregation problems ⋮ Average parameterization and partial kernelization for computing medians ⋮ Partial Kernelization for Rank Aggregation: Theory and Experiments ⋮ Beyond pairwise comparisons in social choice: a setwise Kemeny aggregation problem ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ COMPARING AND AGGREGATING PARTIAL ORDERS WITH KENDALL TAU DISTANCES ⋮ A new approach for identifying the Kemeny median ranking ⋮ Reducing the time required to find the Kemeny ranking by exploiting a necessary condition for being a winner

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of Kemeny elections
• Parameterized complexity of candidate control in elections and related digraph problems
• Voting schemes for which it can be difficult to tell who won the election
• A general method to speed up fixed-parameter-tractable algorithms
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• On complexity of lobbying in multiple referenda
• Parametrized complexity theory.
• Fixed-Parameter Algorithms for Kemeny Scores
• Parameterized Computational Complexity of Dodgson and Young Elections
• Deconstructing Intractability: A Case Study for Interval Constrained Coloring
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Rank Aggregation: Together We're Strong
• Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
• Aggregating inconsistent information

This page was built for publication: Fixed-parameter algorithms for Kemeny rankings