The classical k-means algorithm for paritioning n points in R d into k sub- sets is one of the most popular and widely spread clustering methods in scientific and business applications. The present paper gives a generalization that is capable of handling weighted point sets and prescribed lower and upper bounds on the cluster sizes. The new algorithm replaces the assignment step of k-means by the computation of a weight-balanced least-squares assignment. This is modelled as a linear program over a weight-balanced partition polytope whose optimal vertices correspond to clus- terings that allow strongly feasible power diagrams. We use this correspondence to derive a worst-case upper bound n O(dk) for the number of operations. This is similar to the known upper bound for k-means, polynomial for fixed k and d, and in view of the known complexity results for k-means, essentially the best one can expect. Further, we show the kernelizability of our approach.