On connections between k-coloring and Euclidean k-means

Enver Aman, Karthik C. S., Sharath Punna

In the Euclidean $k$-means problems we are given as input a set of $n$ points in ${\mathbb{R}}^d$ and the goal is to find a set of $k$ points $C\subseteq {\mathbb{R}}^d$, so as to mini…