A constant FPT approximation algorithm for hard-capacitated k-means
From MaRDI portal
Publication:2218871
Abstract: Hard-capacitated -means (HCKM) is one of the fundamental problems remaining open in combinatorial optimization and data mining areas. In this problem, one is required to partition a given -point set into disjoint clusters with known capacity so as to minimize the sum of within-cluster variances. It is known to be at least APX-hard and for which most of the work is from a meta heuristic perspective. To the best our knowledge, no constant approximation algorithm or existence proof of such an algorithm is known. As our main contribution, we propose an FPT() algorithm with performance guarantee of for any HCKM instances in this paper.
Recommendations
- An approximation algorithm for the uniform capacitated \(k\)-means problem
- Approximation algorithms for hard capacitated \(k\)-facility location problems
- An improved approximation algorithm for the hard uniform capacitated k-median problem
- Constant Factor Approximation for Capacitated k-Center with Outliers
- On uniform capacitated k-median beyond the natural LP relaxation
Cites work
- A 1.488 approximation algorithm for the uncapacitated facility location problem
- A local search approximation algorithm for \(k\)-means clustering
- A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
- An approximation algorithm for uniform capacitated k-median problem with 1+ capacity violation
- Approximation Schemes for Capacitated Clustering in Doubling Metrics
- Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Constant-Factor FPT Approximation for Capacitated k-Median
- Grouping Multidimensional Data
- scientific article; zbMATH DE number 6381735 (Why is no real title available?)
- Improved and simplified inapproximability for \(k\)-means
- Least squares quantization in PCM
- Local search yields a PTAS for \(k\)-means in doubling metrics
- Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
- NP-hardness of Euclidean sum-of-squares clustering
- On the fixed-parameter tractability of capacitated clustering
- On uniform capacitated k-median beyond the natural LP relaxation
- On variants of k-means clustering
- The hardness of approximation of Euclidean k-means
Cited in
(14)- An approximation algorithm for the uniform capacitated \(k\)-means problem
- Approximation algorithms for the capacitated correlation clustering problem with penalties
- On parameterized approximation algorithms for balanced clustering
- To close is easier than to open: dual parameterization to \(k\)-median
- Approximation algorithm for the capacitated correlation clustering problem with penalties
- Algorithms and Computation
- Approximation Algorithms for the Capacitated Min–Max Correlation Clustering Problem
- Effective Heuristic Techniques for Combined Robust Clustering Problem
- FPT Approximation for Constrained Metric k-Median/Means
- Approximation algorithms for diversity-bounded center problems
- A semi brute-force search approach for (balanced) clustering
- FPT constant-approximations for capacitated clustering to minimize the sum of cluster radii
- Risk-embedded scheduling optimization for a virtual power plant under carbon emission trading constraints
- Separating \(k\)-\textsc{Median} from the supplier version
This page was built for publication: A constant FPT approximation algorithm for hard-capacitated \(k\)-means
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2218871)
