A Discretization Algorithm for k-Means with Capacity Constraints

We consider capacitated k-means clustering whose object is to minimize the within-cluster sum of squared Euclidean distances. The task is to partition a set of n observations into k disjoint clusters satisfying the capacity constraints, both upper and lower bound capacities are considered. One of the reasons making these clustering problems hard to deal with is the continuous choices of the centroid. In this paper we propose a discretization algorithm that in polynomial time outputs an approximate centroid set with at most \(\epsilon \) fractional loss of the original object. This result implies an FPT(k,d) PTAS for uniform capacitated k-means and makes more techniques, for example local search, possible to apply to it.