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?

  • 1
    $\begingroup$ 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. $\endgroup$ Dec 20, 2021 at 21:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.