Approximation 2-Means/Center Clustering

We release the 2-approximation 2-Center clustering.

2-Center Approximation Algorithm

The problem $k$-Center is defined as follows: Given the set $S$ of points on the Euclidean space, find the $k$ balls $\mathcal B$ such that the union of the balls covers all points of $S$ while minimizing $\text{max}_{v\in S}d(v, B_v)$, where $B_v$ is the ball covering $v$ and $d(\cdot, \cdot)$ is the (Euclidean) distance function. In other words, we want to find the balls minimizing the maximum radii.
The 2-approximation 2-Center algorithm is an algorithm that provides a solution to the 2-Center problem with an approximation factor of 2, i.e., the algorithm guarantees that the objective value of its solution is at most twice the optimal value.
Our algorithm outputs the centers of the solution (i.e., the centers of the balls). It is a basic 2-approximation 2-Center algorithm based on a greedy technique. Specifically, the algorithm works as follows:

1. Pick an arbitrary point in SSS as the first center.
2. Select the farthest point from the first center as the second center.

Full Changelog: v1.0.0...v2.0.0

Approximation 2-Means Clustering

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].