Metric k-center

A simple greedy approximation algorithm that achieves an approximation factor of 2 builds ${\displaystyle {\mathcal {C}}}$ using a farthest-first traversal in k iterations. This algorithm simply chooses the point farthest away from the current set of centers in each iteration as the new center. It can be described as follows:

• Pick an arbitrary point ${\displaystyle {\bar {c}}_{1}}$ into ${\displaystyle C_{1}}$
• For every point ${\displaystyle v\in \mathbf {V} }$ compute ${\displaystyle d_{1}[v]}$ from ${\displaystyle {\bar {c}}_{1}}$
• Pick the point ${\displaystyle {\bar {c}}_{2}}$ with highest distance from ${\displaystyle {\bar {c}}_{1}}$.
• Add it to the set of centers and denote this expanded set of centers as ${\displaystyle C_{2}}$. Continue this till k centers are found

• The i^th iteration of choosing the i^th center takes ${\displaystyle {\mathcal {O}}(n)}$ time.
• There are k such iterations.
• Thus, overall the algorithm takes ${\displaystyle {\mathcal {O}}(nk)}$ time.[3]

The solution obtained using the simple greedy algorithm is a 2-approximation to the optimal solution. This section focuses on proving this approximation factor.

Given a set of n points ${\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}$, belonging to a metric space (${\displaystyle {\mathcal {X}}}$,d), the greedy K-center algorithm computes a set K of k centers, such that K is a 2-approximation to the optimal k-center clustering of V.

i.e. ${\displaystyle r^{\mathbf {K} }(\mathbf {V} )\leq 2r^{opt}(\mathbf {V} ,{\textit {k}})}$ [1]

This theorem can be proven using two cases as follows,

Case 1: Every cluster of ${\displaystyle {\mathcal {C}}_{opt}}$ contains exactly one point of ${\displaystyle \mathbf {K} }$

• Consider a point ${\displaystyle v\in \mathbf {V} }$
• Let ${\displaystyle {\bar {c}}}$ be the center it belongs to in ${\displaystyle {\mathcal {C}}_{opt}}$
• Let ${\displaystyle {\bar {k}}}$ be the center of ${\displaystyle \mathbf {K} }$ that is in ${\displaystyle \Pi ({\mathcal {C}}_{opt},{\bar {c}})}$
• ${\displaystyle d(v,{\bar {c}})=d(v,{\mathcal {C}}_{opt})\leq r^{opt}(\mathbf {V} ,k)}$
• Similarly, ${\displaystyle d({\bar {k}},{\bar {c}})=d({\bar {k}},{\mathcal {C}}_{opt})\leq r^{opt}}$
• By the triangle inequality: ${\displaystyle d(v,{\bar {k}})\leq d(v,{\bar {c}})+d({\bar {c}},{\bar {k}})\leq 2r^{opt}}$

Case 2: There are two centers ${\displaystyle {\bar {k}}}$ and ${\displaystyle {\bar {u}}}$ of ${\displaystyle \mathbf {K} }$ that are both in ${\displaystyle \Pi ({\mathcal {C}}_{opt},{\bar {c}})}$, for some ${\displaystyle {\bar {c}}\in {\mathcal {C}}_{opt}}$ (By pigeon hole principle, this is the only other possibility)

• Assume, without loss of generality, that ${\displaystyle {\bar {u}}}$ was added later to the center set ${\displaystyle \mathbf {K} }$ by the greedy algorithm, say in i^th iteration.
• But since the greedy algorithm always chooses the point furthest away from the current set of centers, we have that ${\displaystyle {\bar {k}}\in {\mathcal {C}}_{i-1}}$and,

${\displaystyle {\begin{aligned}r^{\mathbf {K} }(\mathbf {V} )\leq r^{{\mathcal {C}}_{i-1}}(\mathbf {V} )&=d({\bar {u}},{\mathcal {C}}_{i-1})\\&\leq d({\bar {u}},{\bar {k}})\\&\leq d({\bar {u}},{\bar {c}})+d({\bar {c}},{\bar {k}})\\&\leq 2r^{opt}\end{aligned}}}$ [1]

Another algorithm with the same approximation factor takes advantage of the fact that the k-Center problem is equivalent to finding the smallest index i such that G_i has a dominating set of size at most k and computes a maximal independent set of G_i, looking for the smallest index i that has a maximal independent set with a size of at least k. [4] It is not possible to find an approximation algorithm with an approximation factor of 2 − ε for any ε > 0, unless P = NP. [5] Furthermore, the distances of all edges in G must satisfy the triangle inequality if the k-center problem is to be approximated within any constant factor, unless P = NP. [6]

It can be shown that the k-Center problem is W[2]-hard to approximate within a factor of 2 − ε for any ε > 0, when using k as the parameter.[7] This is also true when parameterizing by the doubling dimension (in fact the dimension of a Manhattan metric), unless P=NP.[8] When considering the combined parameter given by k and the doubling dimension, k-Center is still W[1]-hard but it is possible to obtain a parameterized approximation scheme.[9] This is even possible for the variant with vertex capacities, which bound how many vertices can be assigned to an opened center of the solution.[10]