A balanced k-means algorithm for weighted point sets
  The classical $k$-means algorithm for partitioning $n$ points in
$\mathbb{R}^d$ into $k$ clusters is one of the most popular and widely spread
clustering methods. The need to respect prescribed lower bounds on the cluster
sizes has been observed in many scientific and business applications.
  In this paper, we present and analyze a generalization of $k$-means that is
capable of handling weighted point sets and prescribed lower and upper bounds
on the cluster sizes. We call it weight-balanced $k$-means. The key difference
to existing models lies in the ability to handle the combination of weighted
point sets with prescribed bounds on the cluster sizes. This imposes the need
to perform partial membership clustering, and leads to significant differences.
  For example, while finite termination of all $k$-means variants for
unweighted point sets is a simple consequence of the existence of only finitely
many partitions of a given set of points, the situation is more involved for
weighted point sets, as there are infinitely many partial membership
clusterings. Using polyhedral theory, we show that the number of iterations of
weight-balanced $k$-means is bounded above by $n^{O(dk)}$, so in particular it
is polynomial for fixed $k$ and $d$. This is similar to the known worst-case
upper bound for classical $k$-means for unweighted point sets and unrestricted
cluster sizes, despite the much more general framework. We conclude with the
discussion of some additional favorable properties of our method.
