Partial kernelization for rank aggregation: theory and experiments

DOI10.1007/978-3-642-17493-3_5MaRDI QIDQ3058689zbMATH OpenOpenAlexFDO

Authors Nadja Betzler, Robert Bredereck, Rolf Niedermeier

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

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

Recommendations

• Experiments with Kemeny ranking: What works when?
• Rank aggregation: together we're strong
• Fixed-parameter algorithms for Kemeny rankings
• Fixed-Parameter Algorithms for Kemeny Scores
• An efficient approach for the rank aggregation problem

Cites work

• A Consistent Extension of Condorcet’s Election Principle
• Aggregating inconsistent information: ranking and clustering
• Approximation schemes for the betweenness problem in tournaments and related ranking problems
• Average parameterization and partial kernelization for computing medians
• Deterministic pivoting algorithms for constrained ranking and clustering problems
• Fixed-parameter algorithms for Kemeny rankings
• scientific article; zbMATH DE number 5485441 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Improved parameterized algorithms for the Kemeny aggregation problem
• Parameterizing above or below guaranteed values
• Voting schemes for which it can be difficult to tell who won the election

Cited in

(18)

• Kernel-based learning methods for preference aggregation
• Manipulative elicitation -- a new attack on elections with incomplete preferences
• Partial recovery for top-\(k\) ranking: optimality of MLE and suboptimality of the spectral method
• A new approach for identifying the Kemeny median ranking
• Median constrained bucket order rank aggregation
• An efficient approach for the rank aggregation problem
• Comparing series of rankings with ties by using complex networks: an analysis of the Spanish stock market (IBEX-35 index)
• On the exact amount of missing information that makes finding possible winners hard
• Parameterized enumeration of (locally-) optimal aggregations
• Studies in Computational Aspects of Voting
• Polynomial kernels and user reductions for the workflow satisfiability problem
• Fixed-Parameter Algorithms for Kemeny Scores
• Average parameterization and partial kernelization for computing medians
• Experiments with Kemeny ranking: What works when?
• On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
• Approximate Condorcet partitioning: solving large-scale rank aggregation problems
• Average parameterization and partial kernelization for computing medians
• Kernelization complexity of possible winner and coalitional manipulation problems in voting

This page was built for publication: Partial kernelization for rank aggregation: theory and experiments

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