We release the (1+$\varepsilon$)-approximation 2-Means clustering.
2-Means Approximation Algorithm
The problem $k$-Means is defined as follows: Given the set $S$ of points on the Euclidean space, find the $k$ points $\mathcal C$ minimizing the sum of the square of the distance between each point and its corresponding center, i.e. $\text{min}{v\in S}d(v, \text{argmin}{c\in C}d(v,c))$, where $d(\cdot, \cdot)$ is the (Euclidean) distance function.
The $(1+\varepsilon)$-approximation 2-Means algorithm is an algorithm that provides a solution to the 2-Means problem with an approximation factor of $(1+\varepsilon)$, i.e., the algorithm guarantees that the objective value of its solution is at most twice the optimal value. Note that $\varepsilon$ is also given with the problem instance.
Our algorithm outputs the centers of the solution. It is based on the work of [Kumar, Sabharwal, and Sen 04].
