Partial Kernelization for Rank Aggregation: Theory and Experiments

DOI10.1007/978-3-642-17493-3_5zbMath1309.68083OpenAlexW170444856MaRDI QIDQ3058689

Nadja Betzler, Rolf Niedermeier, Robert Bredereck

Publication date: 7 December 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-17493-3_5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)

Related Items (9)

Manipulative elicitation -- a new attack on elections with incomplete preferences ⋮ Polynomial kernels and user reductions for the workflow satisfiability problem ⋮ Studies in Computational Aspects of Voting ⋮ Kernelization complexity of possible winner and coalitional manipulation problems in voting ⋮ On the exact amount of missing information that makes finding possible winners hard ⋮ Experiments with Kemeny ranking: What works when? ⋮ Average parameterization and partial kernelization for computing medians ⋮ On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard ⋮ Comparing series of rankings with ties by using complex networks: an analysis of the Spanish stock market (IBEX-35 index)

Cites Work

• Unnamed Item
• Unnamed Item
• Average parameterization and partial kernelization for computing medians
• Parameterizing above or below guaranteed values
• Fixed-parameter algorithms for Kemeny rankings
• Voting schemes for which it can be difficult to tell who won the election
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
• Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems
• Improved Parameterized Algorithms for the Kemeny Aggregation Problem
• A Consistent Extension of Condorcet’s Election Principle
• Aggregating inconsistent information

This page was built for publication: Partial Kernelization for Rank Aggregation: Theory and Experiments