Metric k-center

Short description: Combinatorial optimization problem

In graph theory, the metric k-center problem is a combinatorial optimization problem studied in theoretical computer science. Given n cities with specified distances, one wants to build k warehouses in different cities and minimize the maximum distance of a city to a warehouse. In graph theory, this means finding a set of k vertices for which the largest distance of any point to its closest vertex in the k-set is minimum. The vertices must be in a metric space, providing a complete graph that satisfies the triangle inequality.

Formal definition

Let [math]\displaystyle{ (X,d) }[/math] be a metric space where [math]\displaystyle{ X }[/math] is a set and [math]\displaystyle{ d }[/math] is a metric
A set [math]\displaystyle{ \mathbf{V}\subseteq\mathcal{X} }[/math], is provided together with a parameter [math]\displaystyle{ k }[/math]. The goal is to find a subset [math]\displaystyle{ \mathcal{C}\subseteq \mathbf{V} }[/math] with [math]\displaystyle{ |\mathcal{C}|=k }[/math] such that the maximum distance of a point in [math]\displaystyle{ \mathbf{V} }[/math] to the closest point in [math]\displaystyle{ \mathcal{C} }[/math] is minimized. The problem can be formally defined as follows:
For a metric space ([math]\displaystyle{ \mathcal{X} }[/math],d),

• Input: a set [math]\displaystyle{ \mathbf{V}\subseteq\mathcal{X} }[/math], and a parameter [math]\displaystyle{ k }[/math].
• Output: a set [math]\displaystyle{ \mathcal{C}\subseteq\mathbf{V} }[/math] of [math]\displaystyle{ k }[/math] points.
• Goal: Minimize the cost [math]\displaystyle{ r^\mathcal{C}(\mathbf{V}) = \underset{v\in V}{\max} }[/math] d(v,[math]\displaystyle{ \mathcal{C} }[/math])

That is, Every point in a cluster is in distance at most [math]\displaystyle{ r^\mathcal{C}(V) }[/math] from its respective center.

The k-Center Clustering problem can also be defined on a complete undirected graph G = (V, E) as follows:
Given a complete undirected graph G = (V, E) with distances d(v_i, v_j) ∈ N satisfying the triangle inequality, find a subset C ⊆ V with |C| = k while minimizing:

[math]\displaystyle{ \max_{v \in V} \min_{c \in C} d(v,c) }[/math]

Computational complexity

In a complete undirected graph G = (V, E), if we sort the edges in non-decreasing order of the distances: d(e₁) ≤ d(e₂) ≤ ... ≤ d(e_m) and let G_i = (V, E_i), where E_i = {e₁, e₂, ..., e_i}. 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.

Although Dominating Set is NP-complete, the k-center problem remains NP-hard. This is clear, since the optimality of a given feasible solution for the k-center problem can be determined through the Dominating Set reduction only if we know in first place the size of the optimal solution (i.e. the smallest index i such that G_i has a dominating set of size at most k), which is precisely the difficult core of the NP-Hard problems. Although a Turing reduction can get around this issue by trying all values of k.

Approximations

A simple greedy algorithm

A simple greedy approximation algorithm that achieves an approximation factor of 2 builds [math]\displaystyle{ \mathcal{C} }[/math] 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 [math]\displaystyle{ \bar{c}_1 }[/math] into [math]\displaystyle{ C_1 }[/math]
• For every point [math]\displaystyle{ v\in \mathbf{V} }[/math] compute [math]\displaystyle{ d_1[v] }[/math] from [math]\displaystyle{ \bar{c}_1 }[/math]
• Pick the point [math]\displaystyle{ \bar{c}_2 }[/math] with highest distance from [math]\displaystyle{ \bar{c}_1 }[/math].
• Add it to the set of centers and denote this expanded set of centers as [math]\displaystyle{ C_2 }[/math]. Continue this till k centers are found

Running time

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

Proving the approximation factor

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 [math]\displaystyle{ \mathbf{V}\subseteq\mathcal{X} }[/math], belonging to a metric space ([math]\displaystyle{ \mathcal{X} }[/math],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. [math]\displaystyle{ r^{\mathbf{K}}(\mathbf{V})\leq 2r^{opt}(\mathbf{V},\textit{k}) }[/math]

This theorem can be proven using two cases as follows,

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

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

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

• Assume, without loss of generality, that [math]\displaystyle{ \bar{u} }[/math] was added later to the center set [math]\displaystyle{ \mathbf{K} }[/math] 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 [math]\displaystyle{ \bar{k}\in\mathcal{C}_{i-1} }[/math]and,

[math]\displaystyle{ \begin{align} 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{align} }[/math]

Another 2-factor approximation algorithm

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. It is not possible to find an approximation algorithm with an approximation factor of 2 − ε for any ε > 0, unless P = NP. 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.

Parameterized approximations

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. This is also true when parameterizing by the doubling dimension (in fact the dimension of a Manhattan metric), unless P=NP. 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. 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.

See also

• Traveling salesman problem
• Minimum k-cut
• Dominating set
• Independent set (graph theory)
• Facility location problem

Further reading

• Hochbaum; Shmoys (1985), "A Best Possible Heuristic for the k-Center Problem", Mathematics of Operations Research, 10, pp. 180–184, doi:10.1287/moor.10.2.180