In graph theory, the metric k-center problem or vertex k-center problem is a classical combinatorial optimization problem studied in theoretical computer science that is NP-hard. 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. It has application in facility location and clustering.
Formal definition The problem was first proposed by Hakimi in 1964. Let ( X , d ) {\displaystyle (X,d)} be a metric space where X {\displaystyle X} is a set and d {\displaystyle d} is a metric A set V ⊆ X {\displaystyle \mathbf {V} \subseteq {\mathcal {X}}} , is provided together with a parameter k {\displaystyle k} . The goal is to find a subset C ⊆ V {\displaystyle {\mathcal {C}}\subseteq \mathbf {V} } with | C | = k {\displaystyle |{\mathcal {C}}|=k} such that the maximum distance of a point in V {\displaystyle \mathbf {V} } to the closest point in C {\displaystyle {\mathcal {C}}} is minimized. The problem can be formally defined as follows: For a metric space ( X {\displaystyle {\mathcal {X}}} ,d),
Input: a set V ⊆ X {\displaystyle \mathbf {V} \subseteq {\mathcal {X}}} , and a parameter k {\displaystyle k} . Output: a set C ⊆ V {\displaystyle {\mathcal {C}}\subseteq \mathbf {V} } of k {\displaystyle k} points. Goal: Minimize the cost r C ( V ) = max v ∈ V {\displaystyle r^{\mathcal {C}}(\mathbf {V} )={\underset {v\in V}{\max }}} d(v, C {\displaystyle {\mathcal {C}}} ) That is, every point in a cluster is in distance at most r C ( V ) {\displaystyle r^{\mathcal {C}}(V)} 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(vi, vj) ∈ N satisfying the triangle inequality, find a subset C ⊆ V with |C| = k while minimizing:
max v ∈ V min c ∈ C d ( v , c ) {\displaystyle \max _{v\in V}\min _{c\in C}d(v,c)}
Computational complexity In a complete undirected graph G = (V, E), if we sort the edges in non-decreasing order of the distances: d(e1) ≤ d(e2) ≤ ... ≤ d(em) and let Gi = (V, Ei), where Ei = {e1, e2, ..., ei}. The k-center problem is equivalent to finding the smallest index i such that Gi 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 Gi 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 C {\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 c ¯ 1 {\displaystyle {\bar {c}}_{1}} into C 1 {\displaystyle C_{1}}
For every point v ∈ V {\displaystyle v\in \mathbf {V} } compute d 1 [ v ] {\displaystyle d_{1}[v]} from c ¯ 1 {\displaystyle {\bar {c}}_{1}}
… excerpt ends here. Continue reading the full article.
