Faster Balanced Clusterings in High Dimension
  The problem of constrained clustering has attracted significant attention in
the past decades. In this paper, we study the balanced $k$-center, $k$-median,
and $k$-means clustering problems where the size of each cluster is constrained
by the given lower and upper bounds. The problems are motivated by the
applications in processing large-scale data in high dimension. Existing methods
often need to compute complicated matchings (or min cost flows) to satisfy the
balance constraint, and thus suffer from high complexities especially in high
dimension. We develop an effective framework for the three balanced clustering
problems to address this issue, and our method is based on a novel spatial
partition idea in geometry. For the balanced $k$-center clustering, we provide
a $4$-approximation algorithm that improves the existing approximation factors;
for the balanced $k$-median and $k$-means clusterings, our algorithms yield
constant and $(1+\epsilon)$-approximation factors with any $\epsilon>0$. More
importantly, our algorithms achieve linear or nearly linear running times when
$k$ is a constant, and significantly improve the existing ones. Our results can
be easily extended to metric balanced clusterings and the running times are
sub-linear in terms of the complexity of $n$-point metric.
