Improved PTAS for the constrained k-means problem

The k-means problem has been paid lots of attention in many fields, and each cluster of the k-means problem always satisfies locality property. In this paper, we study the constrained k-means problem, where the clusters do not satisfy locality property and can be an arbitrary partition of the set of points. Ding and Xu presented a unified framework with running time $$O(2^{poly (k/\epsilon )} (\log n)^{k+1} nd)$$ O ( 2 p o l y ( k / ϵ ) ( log n ) k + 1 n d ) by applying uniform sampling and simplex lemma techniques such that a collection of size $$O(2^{poly (k/\epsilon )} (\log n)^{k+1})$$ O ( 2 p o l y ( k / ϵ ) ( log n ) k + 1 ) of candidate sets containing approximate centers is obtained. Then, the collection is enumerated to get the one that can induce a $$(1+\epsilon )$$ ( 1 + ϵ ) -approximation solution for the constrained k-means problem. By applying $$D^2$$ D 2 -sampling technique, Bhattacharya, Jaiswal, and Kumar presented an algorithm with running time $$O(2^{{\tilde{O}}(k/\epsilon )}nd)$$ O ( 2 O ~ ( k / ϵ ) n d ) , which is bounded by $$O(2^k( \frac{2123ek}{\epsilon ^3})^{64k/\epsilon }knd)$$ O ( 2 k ( 2123 e k ϵ 3 ) 64 k / ϵ k n d ) . The algorithm outputs a collection of size $$O(2^k( \frac{2123ek}{\epsilon ^3})^{64k/\epsilon })$$ O ( 2 k ( 2123 e k ϵ 3 ) 64 k / ϵ ) of candidate sets containing approximate centers. In this paper, we present an algorithm with running time $$O((\frac{1891ek}{\epsilon ^2})^{8k/\epsilon }nd)$$ O ( ( 1891 e k ϵ 2 ) 8 k / ϵ n d ) such that a collection of size $$O((\frac{1891ek}{\epsilon ^2})^{8k/\epsilon }n)$$ O ( ( 1891 e k ϵ 2 ) 8 k / ϵ n ) of candidate sets containing approximate centers can be obtained.