FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii

Abstract

Clustering with capacity constraints is a fundamental problem that attracted significant attention throughout the years. In this paper, we give the first FPT constant-factor approximation algorithm for the problem of clustering points in a general metric into $k$ clusters to minimize the sum of cluster radii, subject to non-uniform hard capacity constraints. In particular, we give a $(15+\hat{I}\mu )$-approximation algorithm that runs in $2^{0(k^2\log k)}\cdot n^3$ time. When capacities are uniform, we obtain the following improved approximation bounds: A (4 + $\hat{I}\mu$)-approximation with running time $2^{O(k\log (k/\hat{I}\mu ))}{n}^3$, which significantly improves over the FPT 28-approximation of Inamdar and Varadarajan [ESA 2020]; a (2 + $\hat{I}\mu$)-approximation with running time $2^{O(k/\hat{I}{\mu }^2\cdot \log (k/\hat{I}\mu ))}d{n}^3$ and a $(1+\hat{I}\mu )$-approximation with running time $2^{O(kd\log ((k/\hat{I}\mu )))}{n}^3$ in the Euclidean space; and a (1 + $\hat{I}\mu$)-approximation in the Euclidean space with running time $2^{O(k/\hat{I}{\mu }^2\cdot \log (k/\hat{I}\mu ))}d{n}^3$ if we are allowed to violate the capacities by (1 + $\hat{I}\mu$)-factor. We complement this result by showing that there is no (1 + $\hat{I}\mu$)-approximation algorithm running in time $f(k)\cdot n^{O(1)}$, if any capacity violation is not allowed.

Updated version: fix an error in the proof of Lemma 2.5