Constant-Factor FPT Approximation for Capacitated k-Median
From MaRDI portal
Publication:5075732
DOI10.4230/LIPIcs.ESA.2019.1OpenAlexW2977708045MaRDI QIDQ5075732
Marek Adamczyk, Jan Marcinkowski, Michał Włodarczyk, Jaroslaw Byrka, Syed M. Meesum
Publication date: 11 May 2022
Full work available at URL: https://arxiv.org/abs/1809.05791
Related Items (8)
Improved parameterized approximation for balanced \(k\)-median ⋮ Unnamed Item ⋮ A constant FPT approximation algorithm for hard-capacitated \(k\)-means ⋮ A unified framework of FPT approximation algorithms for clustering problems ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ Constant-Factor FPT Approximation for Capacitated k-Median ⋮ On parameterized approximation algorithms for balanced clustering ⋮ To close is easier than to open: dual parameterization to \(k\)-median
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Small space representations for metric min-sum \(k\)-clustering and their applications
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Approximation algorithms for hard capacitated \(k\)-facility location problems
- 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
- 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
- Constant-Factor FPT Approximation for Capacitated k-Median
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
- On the parameterized complexity of approximating dominating set
- On Uniform Capacitated k-Median Beyond the Natural LP Relaxation
- Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems
- An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
- Approximating k-median via pseudo-approximation
- A tight bound on approximating arbitrary metrics by tree metrics
This page was built for publication: Constant-Factor FPT Approximation for Capacitated k-Median
