Speeding Up Constrained $k$-Means Through 2-Means

Abstract

For the constrained 2-means problem, we present a $O\left(dn+d(\frac{1}{\epsilon }{)}^{O(\frac{1}{\epsilon })}\log n\right)$ time algorithm. It generates a collection $U$ of approximate center pairs $(c_1,c_2)$ such that one of pairs in $U$ can induce a $(1+\epsilon )$-approximation for the problem. The existing approximation scheme for the constrained 2-means problem takes $O((\frac{1}{\epsilon }{)}^{O(\frac{1}{\epsilon })}dn)$ time, and the existing approximation scheme for the constrained $k$-means problem takes $O((\frac{k}{\epsilon }{)}^{O(\frac{k}{\epsilon })}dn)$ time. Using the method developed in this paper, we point out that every existing approximating scheme for the constrained $k$-means so far with time $C(k,n,d,\epsilon )$ can be transformed to a new approximation scheme with time complexity $C(k,n,d,\epsilon )/k^{\Omega (\frac{1}{\epsilon })}$.