To close is easier than to open: dual parameterization to \(k\)-median
From MaRDI portal
Publication:2117693
DOI10.1007/978-3-030-80879-2_8OpenAlexW3184443380MaRDI QIDQ2117693
Michał Włodarczyk, Pasin Manurangsi, Jan Marcinkowski, Szymon Dudycz, Jaroslaw Byrka
Publication date: 22 March 2022
Full work available at URL: https://arxiv.org/abs/2011.08083
Cites Work
- A tight lower bound for planar Steiner orientation
- A constant FPT approximation algorithm for hard-capacitated \(k\)-means
- A constant-factor approximation algorithm for the k -median problem (extended abstract)
- An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation
- Greedy Strikes Back: Improved Facility Location Algorithms
- Color-coding
- Analysis of a Local Search Heuristic for Facility Location Problems
- Approximating capacitated k-median with (1 + ∊)k open facilities
- Local Search Heuristics for k-Median and Facility Location Problems
- Lossy kernelization
- Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
- Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
- Constant-Factor FPT Approximation for Capacitated k-Median
- Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
- Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
- On Uniform Capacitated k-Median Beyond the Natural LP Relaxation
- An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
- Parameterized Algorithms
- SOFSEM 2006: Theory and Practice of Computer Science
- A tight bound on approximating arbitrary metrics by tree metrics
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: To close is easier than to open: dual parameterization to \(k\)-median
