# K-means, but normalized and with max

Given points $$x_1, \ldots, x_n$$ in the Euclidean space and $$K \in \mathbb N$$, I'm interested in the following objective. Partition the points into $$K$$ clusters $$C_1, \ldots, C_K$$ so that: $$\max_{i \in [K]} \frac{1}{|C_i|}\sum_{j \in C_i} \|x_j - \mu(C_i))\|^2$$ is minimized, where $$\mu(C_i) = \frac{1}{|C_i|} \sum_{j \in C_i} x_j$$. So it's similar to k-means, but it has $$\max$$ instead of sum, and the term for each cluster is normalized. Intuitively, I want to minimize $$\max_i Var[C_i]$$.

Does this problem have a name? Is there a known approximation for this problem?

• Without normalization, the problem is known as the Minimum Load Clustering problem. In Euclidean space, it has been studied here. Overall, this problem has been barely studied. Therefore, less chance to find your version of the problem. Dec 20, 2021 at 21:23