On the fixed-parameter tractability of capacitated clustering
From MaRDI portal
Publication:5091191
Recommendations
Cites work
- A constant-factor approximation algorithm for the k-median problem
- An approximation algorithm for uniform capacitated k-median problem with 1+ capacity violation
- An FPT algorithm beating 2-approximation for \(k\)-cut
- Approximating k-median with non-uniform capacities
- Approximating capacitated \(k\)-median with \((1 + \epsilon)k\) open facilities
- Approximation Schemes for Capacitated Clustering in Doubling Metrics
- Approximation schemes for clustering problems
- Bi-factor approximation algorithms for hard capacitated k-median problems
- Coresets in dynamic geometric data streams
- scientific article; zbMATH DE number 1775394 (Why is no real title available?)
- scientific article; zbMATH DE number 1775395 (Why is no real title available?)
- scientific article; zbMATH DE number 6850339 (Why is no real title available?)
- scientific article; zbMATH DE number 7561535 (Why is no real title available?)
- Linear-time approximation schemes for clustering problems in any dimensions
- Losing Treewidth by Separating Subsets
- Nonlinear dimension reduction via outer bi-Lipschitz extensions
- On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
- On coresets for k-means and k-median clustering
- On uniform capacitated k-median beyond the natural LP relaxation
- On uniform capacitated \(k\)-median beyond the natural LP relaxation
- Optimal terminal dimensionality reduction in Euclidean space
- Partitioning a graph into small pieces with applications to path transversal
- Smaller coresets for k-median and k-means clustering
Cited in
(34)- Lossy kernelization of same-size clustering
- 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 FPT Approximation for Capacitated k-Median
- Approximation Schemes for Capacitated Clustering in Doubling Metrics
- scientific article; zbMATH DE number 7651201 (Why is no real title available?)
- A unified framework of FPT approximation algorithms for clustering problems
- Hardness of approximation for Euclidean \(k\)-median
- FPT Approximation for Constrained Metric k-Median/Means
- Parameterized complexity of categorical clustering with size constraints
- Tight FPT approximation for socially fair clustering
- Lossy kernelization of same-size clustering
- A semi brute-force search approach for (balanced) clustering
- k-median/means with outliers revisited: a simple fpt approximation
- 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 under a knapsack constraint: parameterized approximation for the knapsack median problem
- Clustering what matters in constrained settings (improved outlier to outlier-free reductions)
- Clustering what matters in constrained settings: improved outlier to outlier-free reductions
- FPT approximation for fair minimum-load clustering
- Clustering with a knapsack constraint: parameterized approximation algorithms for the knapsack median problem
- Separating \(k\)-\textsc{Median} from the supplier version
- On coresets for fair clustering in metric and Euclidean spaces and their applications
- FPT approximations for fair k-min-sum-radii
- Parameterized approximation schemes for fair-range clustering
- Dimension-free parameterized approximation schemes for hybrid clustering
- A parameterized approximation algorithm for the diversity-aware l-centrum problem
- Coresets for robust clustering via black-box reductions to vanilla case
- Solving capacitated clustering problems
- Parameterized complexity of categorical clustering with size constraints
This page was built for publication: On the fixed-parameter tractability of capacitated clustering
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091191)
