Constant-Factor FPT Approximation for Capacitated k-Median
From MaRDI portal
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)
- A tight bound on approximating arbitrary metrics by tree metrics
- An approximation algorithm for uniform capacitated k-median problem with 1+ capacity violation
- An FPT algorithm beating 2-approximation for \(k\)-cut
- An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
- Analysis of a Local Search Heuristic for Facility Location Problems
- Approximating k-median with non-uniform capacities
- Approximating capacitated \(k\)-median with \((1 + \epsilon)k\) open facilities
- Approximating k-median via pseudo-approximation
- Approximation algorithms for hard capacitated \(k\)-facility location problems
- Bi-factor approximation algorithms for hard capacitated k-median problems
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Constant approximation for capacitated \(k\)-median with \((1+\epsilon)\)-capacity violation
- Constant-Factor FPT Approximation for Capacitated k-Median
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- scientific article; zbMATH DE number 1775395 (Why is no real title available?)
- Local Search Heuristics for k-Median and Facility Location Problems
- On the fixed-parameter tractability of capacitated clustering
- On the parameterized complexity of approximating dominating set
- On uniform capacitated \(k\)-median beyond the natural LP relaxation
- Small space representations for metric min-sum k-clustering and their applications
Cited in
(20)- On parameterized approximation algorithms for balanced clustering
- To close is easier than to open: dual parameterization to \(k\)-median
- Improved parameterized approximation for balanced \(k\)-median
- A constant FPT approximation algorithm for hard-capacitated \(k\)-means
- Constant Factor Approximation for Capacitated k-Center with Outliers
- Constant-Factor FPT Approximation for Capacitated k-Median
- On the fixed-parameter tractability of capacitated clustering
- A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median
- scientific article; zbMATH DE number 7651201 (Why is no real title available?)
- A unified framework of FPT approximation algorithms for clustering problems
- FPT Approximation for Constrained Metric k-Median/Means
- A PTAS framework for clustering problems in doubling metrics
- FPT constant-approximations for capacitated clustering to minimize the sum of cluster radii
- FPT approximation for capacitated clustering with outliers
- Parameterized inapproximability for Steiner orientation by gap amplification
- A fixed-parameter tractable approximation for capacitated k-supplier
- Clustering with a knapsack constraint: parameterized approximation algorithms for the knapsack median problem
- Separating \(k\)-\textsc{Median} from the supplier version
- Achieving anonymity via weak lower bound constraints for k-median and k-means
- FPT approximations for fair k-min-sum-radii
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)
