Speeding Up Constrained k-Means Through 2-Means

For the constrained 2-means problem, we present a \(O\left( dn+ d({1\over \epsilon })^{O({1\over \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(({1\over \epsilon })^{O({1\over \epsilon })}dn)\) time, and the existing approximation scheme for the constrained k-means problem takes \(O(({k\over \epsilon })^{O({k\over \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^{\varOmega ({1\over \epsilon })}}\) .