  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^{\Omega({1\over\epsilon})}}$.
