Average parameterization and partial kernelization for computing medians

DOI10.1016/J.JCSS.2010.07.005zbMath1215.68107OpenAlexW2058293112MaRDI QIDQ716309

Rolf Niedermeier, Jiong Guo, Nadja Betzler, Christian Komusiewicz

Publication date: 28 April 2011

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.07.005

zbMATH Keywords

data reductionfixed-parameter tractabilityrank aggregationpolynomial-time preprocessingconsensus clustering

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Voting theory (91B12)

Related Items (16)

The linear ordering problem revisited ⋮ Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks ⋮ Studies in Computational Aspects of Voting ⋮ Prices matter for the parameterized complexity of shift bribery ⋮ Space reduction constraints for the median of permutations problem ⋮ A unifying rank aggregation framework to suitably and efficiently aggregate any kind of rankings ⋮ Voting rules as error-correcting codes ⋮ Sampling and learning Mallows and generalized Mallows models under the Cayley distance ⋮ Exploring the median of permutations problem ⋮ Automedian sets of permutations: direct sum and shuffle ⋮ Cluster editing: kernelization based on edge cuts ⋮ Partially Polynomial Kernels for Set Cover and Test Cover ⋮ On the parameterized complexity of consensus clustering ⋮ Partial Kernelization for Rank Aggregation: Theory and Experiments ⋮ Medians of Permutations: Building Constraints ⋮ Cluster Editing in Multi-Layer and Temporal Graphs.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of Kemeny elections
• Pattern matching with address errors: rearrangement distances
• On the approximation of correlation clustering and consensus clustering
• Fixed-parameter algorithms for Kemeny rankings
• NP-hard problems in hierarchical-tree clustering
• Voting schemes for which it can be difficult to tell who won the election
• Consensus clustering: A resampling-based method for class discovery and visualization of gene expression microarray data
• Aggregation of partial rankings, \(p\)-ratings and top-\(m\) lists
• Multiple genome rearrangement by swaps and by element duplications
• Parametrized complexity theory.
• Partial Kernelization for Rank Aggregation: Theory and Experiments
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems
• Closest Substring Problems with Small Distances
• Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
• Kernelization: New Upper and Lower Bound Techniques
• Improved Parameterized Algorithms for the Kemeny Aggregation Problem
• Rank Aggregation: Together We're Strong
• Aggregating inconsistent information

This page was built for publication: Average parameterization and partial kernelization for computing medians