Metric K-center

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

Formal definition

Let $(X,d)$ be a metric space where $X$ is a set and $d$ is a metric

A set $\mathbf\subseteq\mathcal$, is provided together with a parameter $k$. The goal is to find a subset $\mathcal\subseteq \mathbf$ with $, \mathcal, =k$ such that the maximum distance of a point in $\mathbf$ to the closest point in $\mathcal$ is minimized. The problem can be formally defined as follows:

For a metric space ($\mathcal$,d),

* Input: a set $\mathbf\subseteq\mathcal$, and a parameter $k$.
* Output: a set $\mathcal\subseteq\mathbf$ of $k$ points.
* Goal: Minimize the cost $r^\mathcal(\mathbf) = \underset$ d(v,$\mathcal$)

That is, Every point in a cluster is in distance at most $r^\mathcal(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''(''v''_''i'', ''v''_''j'') ∈ ''N'' satisfying the triangle inequality, find a subset ''C'' ⊆ ''V'' with , ''C'',  = ''k'' while minimizing:

: $\max_ \min_ 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''(''e''₁) ≤ ''d''(''e''₂) ≤ … ≤ ''d''(''e''_m) and let ''G''_i = (V, ''E''_i), where ''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 $\mathcal$ 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 $\bar_1$ into $C_1$
* For every point $v\in \mathbf$ compute d_1 /math> from $\bar_1$
* Pick the point $\bar_2$ with highest distance from $\bar_1$.
* Add it to the set of centers and denote this expanded set of centers as $C_2$. Continue this till ''k'' centers are found

Running time

* The i^th iteration of choosing the i^th center takes $\mathcal(n)$ time.
* There are ''k'' such iterations.
* Thus, overall the algorithm takes $\mathcal(nk)$ 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 $\mathbf\subseteq\mathcal$, belonging to a metric space ($\mathcal$,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.'' $r^(\mathbf)\leq 2r^(\mathbf,\textit)$

This theorem can be proven using two cases as follows,

Case 1: Every cluster of $\mathcal_$ contains exactly one point of $\mathbf$

* Consider a point $v\in \mathbf$
* Let $\bar$ be the center it belongs to in $\mathcal_$
* Let $\bar$ be the center of $\mathbf$ that is in $\Pi(\mathcal_,\bar)$
* $d(v,\bar)=d(v,\mathcal_)\leq r^(\mathbf,k)$
* Similarly, $d(\bar,\bar)=d(\bar,\mathcal_)\leq r^$
* By the triangle inequality: $d(v,\bar)\leq d(v,\bar)+d(\bar,\bar)\leq 2r^$


Case 2: There are two centers $\bar$ and $\bar$ of $\mathbf$ that are both in $\Pi(\mathcal_,\bar)$, for some $\bar\in \mathcal_$ (By pigeon hole principle, this is the only other possibility)
* Assume, without loss of generality, that $\bar$ was added later to the center set $\mathbf$ 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 $\bar\in\mathcal_$and,
$\begin r^\mathbf(\mathbf)\leq r^(\mathbf)&=d(\bar,\mathcal_)\\ &\leq d(\bar,\bar)\\ &\leq d(\bar,\bar)+d(\bar,\bar)\\ &\leq 2r^ \end$

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

References

Further reading

* {{citation
, last1 = Hochbaum
, first1 = Dorit S. , author1-link = Dorit S. Hochbaum
, last2 = Shmoys
, first2 = David B. , author2-link = David Shmoys
, contribution = A Best Possible Heuristic for the k-Center Problem
, title = Mathematics of Operations Research
, year = 1985
, volume = 10
, issue = 2
, pages = 180–184

Combinatorial optimization
Computational problems in graph theory
Approximation algorithms
NP-hard problems