Constant-Factor FPT Approximation for Capacitated k-Median
From MaRDI portal
Publication:5075732
DOI10.4230/LIPICS.ESA.2019.1OpenAlexW2977708045MaRDI QIDQ5075732FDOQ5075732
Authors: Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Michał Włodarczyk, S. M. Meesum 
Publication date: 11 May 2022
Full work available at URL: https://arxiv.org/abs/1809.05791
Recommendations
- Constant approximation for capacitated \(k\)-median with \((1+\epsilon)\)-capacity violation
- Bi-factor approximation algorithms for hard capacitated \(k\)-median problems
- Approximating capacitated \(k\)-median with \((1 + \epsilon)k\) open facilities
- On the fixed-parameter tractability of capacitated clustering
- Approximating \(k\)-median with non-uniform capacities
Cites Work
- A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
- Approximating k-median via pseudo-approximation
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A tight bound on approximating arbitrary metrics by tree metrics
- Approximation algorithms for hard capacitated \(k\)-facility location problems
- Local Search Heuristics for k-Median and Facility Location Problems
- An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
- Analysis of a Local Search Heuristic for Facility Location Problems
- On the parameterized complexity of approximating dominating set
- Title not available (Why is that?)
- Approximating \(k\)-median with non-uniform capacities
- On the fixed-parameter tractability of capacitated clustering
- An approximation algorithm for uniform capacitated \(k\)-median problem with \(1+\epsilon\) capacity violation
- Constant approximation for capacitated \(k\)-median with \((1+\epsilon)\)-capacity violation
- Bi-factor approximation algorithms for hard capacitated \(k\)-median problems
- Small space representations for metric min-sum \(k\)-clustering and their applications
- Approximating capacitated \(k\)-median with \((1 + \epsilon)k\) open facilities
- An FPT algorithm beating 2-approximation for \(k\)-cut
- On uniform capacitated \(k\)-median beyond the natural LP relaxation
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Constant-Factor FPT Approximation for Capacitated k-Median
Cited In (14)
- A constant FPT approximation algorithm for hard-capacitated \(k\)-means
- On the fixed-parameter tractability of capacitated clustering
- On parameterized approximation algorithms for balanced clustering
- To close is easier than to open: dual parameterization to \(k\)-median
- Title not available (Why is that?)
- A PTAS framework for clustering problems in doubling metrics
- A unified framework of FPT approximation algorithms for clustering problems
- FPT Approximation for Constrained Metric k-Median/Means
- Improved parameterized approximation for balanced \(k\)-median
- FPT constant-approximations for capacitated clustering to minimize the sum of cluster radii
- Constant Factor Approximation for Capacitated k-Center with Outliers
- Constant-Factor FPT Approximation for Capacitated k-Median
- A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median
- FPT approximation for capacitated clustering with outliers
This page was built for publication: Constant-Factor FPT Approximation for Capacitated k-Median
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075732)
