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

Qilong Feng, Bin Fu

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 $(…