Average parameterization and partial kernelization for computing medians
From MaRDI portal
Publication:716309
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
data reductionfixed-parameter tractabilityrank aggregationpolynomial-time preprocessingconsensus clustering
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
