A constant FPT approximation algorithm for hard-capacitated k-means
Yicheng Xu, Rolf H. Möhring, Dachuan Xu, Yong Zhang, Yifei Zou · arXiv (Cornell University) · 2019
Hard-capacitated $k$-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 $n$-point set into $k$ 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($k$) algorithm with performance guarantee of $69+ε$ for any HCKM instances in this paper.