The \(k\)-center problem
Consider the following problem. A rural district contains several small towns connected by roads. We must build \(k\) hospitals so as to minimize the maximum distance from any town to its nearest hospital. We call this the \(k\)-center problem. This chapter treats the \(k\)-center problem and its weighted version, under the assumption that distances between towns satisfy the triangle inequality. Without this restriction, no \(\alpha (n)\)-approximation algorithm exists for the \(k\)-center problem, for any polynomially computable function \(\alpha (n)\), assuming \(P \neq N P\).
Given an arbitrary subset of vertices \(S \subseteq V\) and an arbitrary vertex \(v \in V\), define the distance from \(v\) to \(S\) as
\[ \operatorname {connect}(v, S) := \min \{ \operatorname {cost}(u, v) \mid u \in S\} \]
The metric \(k\)-center problem
\(I = \left(G, \operatorname {cost}, k\right)\), where
\(G=(V, E)\) is a complete graph;
edge costs \(\operatorname {cost}: E \rightarrow \mathbf{Q}^{+}\) such that for any three vertices \(u, v\) and \(w\)
\[ \operatorname {cost}(u, v) \leq \operatorname {cost}(u, w)+\operatorname {cost}(w, v) \]
a natural number \(k \in \mathbb {N}\) (\(k \leq \left|V\right|\)), fixing the size of \(S\).
A subset of vertices \(S \subseteq V\), with \(|S|=k\), minimizing the quantity \[ \max _{v \in V} \left\{ \operatorname {connect}(v,S)\right\} \]
The metric \(k\)-center problem: an example
A complete graph on \(17\) vertices, \(k=3\) (only some edges are shown for clarity). Hover over a vertex to see which center it is assigned to.
1 Parametric pruning for the metric \(k\)-center problem
Knowing the cost of an optimal solution often makes it easier to find a good approximate solution. In particular, it lets us discard clearly unsuitable inputs and narrow the search space. Unfortunately, computing the cost of an optimal solution is just as hard as finding the solution itself for an NP-hard optimization problem. The technique of parametric pruning allows us to work around this difficulty for some problems. We choose a parameter \(t\), which is a guess for the cost of the optimal solution. For the chosen value of \(t\), from the given instance \(I\) we remove any data that cannot be used in any solution of cost at most \(t\). We denote such a pruned instance by \(I(t)\).
The algorithm rests on several ideas. Let an individual problem \(I\) be given.
Parametrization. Obtain a parametrized decision problem (i.e., a problem with a βYESβ/βNOβ answer) \(\operatorname {decision}(I, t)\) for the original optimization problem:
\(\operatorname {optimization}(I)\): minimize (maximize) the cost of the solution;
\(\operatorname {decision}(I, t)\): determine whether there is a feasible solution of cost \(\operatorname {cost} \leq t\) (\(\operatorname {cost} \geq t\)).
Reduce the optimization problem to the decision problem \(\operatorname {decision}(t)\): solve \(\operatorname {decision}(t)\) for increasing \(t\) until we get the answer βYESβ.
Parameter pruning. When considering \(\operatorname {decision}(I, t)\) for fixed \(I, t\), pass from \(I\) to an individual problem \(I' = I'(t)\) by removing those parts of \(I\) that clearly cannot be used in a feasible solution \(\sigma\) with \(\operatorname {cost}(\sigma ) \leq t\).
Lower bound. An \(\alpha\)-approximation algorithm consists of 2 steps:
the family of instances \(I(t)\) is used to compute a lower bound on \(\operatorname {OPT}\), call it \(t^{*}\);
a feasible solution is found on the instance \(I\left(\alpha \cdot t^{*}\right)\).
Let us show how to apply the parametric pruning technique to the \(k\)-center problem. Number the edges of the graph \(G\) in nondecreasing order of cost, i.e.,
\[ \operatorname {cost}\left(e_{1}\right) \leq \operatorname {cost}\left(e_{2}\right) \leq \ldots \leq \operatorname {cost}\left(e_{m}\right), \]
and let \(G_{i}=\left(V, E_{i}\right)\), where \(E_{i}=\left\{ e_{1}, e_{2}, \ldots , e_{i}\right\}\).
Parametrization. Instead of the original problem we consider the following decision problem \(\operatorname {decision}(I,t)\): given \(I = (G, \operatorname {cost}, k)\) and given \(t \in \mathbb {Q}_+\), determine whether \(G\) has a subset of vertices \(S \subset V\) such that
\[ \max _{v \in V} \left\{ \operatorname {connect}(v,S)\right\} \leq t \]
Note that it suffices to solve \(\operatorname {decision}(I, t)\) for \(t \in \left\{ \operatorname {cost}(e) \mid e \in E\right\}\). Let \(t = \operatorname {cost}(e_j)\) for some \(j = 1, \ldots , m\).
Parameter pruning. When considering the decision problem \(\operatorname {decision}(I,t)\) above, edges whose cost exceeds \(t = \operatorname {cost}(e_j)\) do not affect the answer. They can be removed from the individual problem \(I\): we pass to \(I' = I_j = (G_j, \operatorname {cost}_j, k)\), where
\(G_j = (V, E_j)\);
\(\operatorname {cost}_j = \operatorname {cost}|_{E_j}\).
We pass from \(\operatorname {decision}(I,t)\) to \(\operatorname {decision}(I_j,t)\).
Parametric pruning for the \(k\)-center problem
The solution \(\{s_1,s_2,s_3\}\) (green); blue edges are stars centered at \(S\); the red edge \(e_j\) is the most expensive of them. On the right, the pruned graph \(G_j=(V,\{e_1,\ldots,e_j\})\): every edge more expensive than \(\mathrm{cost}(e_j)\) has been removed. Hover over an edge to see whether it survives the pruning.
A dominating set in an undirected graph \(H=(U, F)\) is a subset \(S \subset U\) such that every vertex in \(U \setminus S\) is adjacent to some vertex in \(S\). Denote by \(\operatorname {dom}(H)\) the size of a minimum (by cardinality) dominating set in \(H\). Note that the problem \(\operatorname {decision}(I_j, \operatorname {cost}(e_j))\) is, in essence, the problem of checking the inequality \(\operatorname {dom}(G_j) \leq k\).
The \(k\)-center problem is equivalent to finding the minimum index \(j\) such that \(G_{j}\) contains a dominating set of size at most \(k\), i.e., \(G_{j}\) contains \(k\) stars covering all vertices, where a star is a graph \(K_{1, p}, p \geq 1\). If \(j^{*}\) is the minimum such index, then the quantity \(\operatorname {cost}\left(e_{j^{*}}\right)\) is the optimal value of the \(k\)-center problem. Denote this quantity by \(\operatorname {OPT}\).
Reducing the original problem to computing \(\operatorname {dom}(G_j)\) does not directly help us: computing the size of a dominating set for an arbitrary graph is an NP-hard problem.
An independent set in a graph \(H=(U, F)\) is a subset of vertices \(I \subset U\) containing no adjacent vertices.
Call the square of a graph \(H=(V, F)\) the graph \(H^{2}=(V, E)\) such that the edge \((u, v) \in E\) if and only if \(H\) contains a path between vertices \(u\) and \(v, u \neq v\), of length at most 2.
The square of a graph
In \(G_j^2\), vertex \(u\) is joined not only to its neighbors (bold edges) but also to their neighbors β to everyone reachable by a path of length \(\le2\) (light arcs). For example, \(u\) and \(u'\) are not adjacent in \(G_j\), but are joined in \(G_j^2\). Hover over a vertex in the right-hand panel.
Let us give an example showing that this bound is tight. Consider a graph on \(n+1\) vertices with a single central vertex. Edges incident to the central vertex have cost 1, and all other edges have cost 2. An example of such a graph is shown in the figure below.
Tightness of the factor-2 bound for the Hochbaum-Shmoys algorithm
A star \(K_{1,n}\): edges at the center \(c\) cost \(1\), all others cost \(2\) (dotted, only some shown). For \(k=1\), the optimum is the center, \(\mathrm{OPT}=1\). The algorithm stops at some \(j\) where \(G_j\) is a star of unit edges and \(G_j^2\) is a complete graph: any vertex is a maximal independent set. Click a vertex to choose it as the center.
For \(k=1\) the optimal solution is the central vertex, and \(\operatorname {OPT}=1\). The HochbaumβShmoys algorithm will obtain index \(j=n\). The graph \(G_{n}^{2}\) is a complete graph, and if a non-central vertex is chosen as the maximal independent set, the cost of the solution obtained by the algorithm will be 2.
2 The weighted \(k\)-center problem
The parametric pruning technique can also be used to solve the metric weighted-center problem.
The metric weighted-center problem
a complete graph \(G=(V, E)\);
edge costs \(\operatorname {cost}: E \rightarrow \mathbf{Q}^{+}\) such that for any three vertices \(u, v\) and \(w\), \(\operatorname {cost}(u, v) \leq\) \(\operatorname {cost}(u, w)+\operatorname {cost}(w, v)\);
vertex weights \(w: V \rightarrow \mathbf{R}^{+}\) and an upper bound \(W \in \mathbf{R}^{+}\).
A set \(S \subseteq V\) of total weight \(w(S) \leq W\) that minimizes the quantity \(\max_{v}\{ \operatorname {connect}(v, S)\}\).
The weighted centers problem
Vertex weights \(1\), \(2\), \(3\) are labeled on the vertices; the upper bound on the total weight of the centers is \(W=4\). Green vertices are the chosen centers, yellow edges are their stars. Hover over a vertex to see its weight and its center.
Denote by \(w \operatorname {dom}(G)\) the weight of a minimum-weight dominating set in the graph \(G\). To solve the metric weighted-center problem, we must find the smallest index \(i\) such that \(w \operatorname {dom}\left(G_{i}\right) \leq\) \(W\). Let this be the index \(i^{*}\); then the cost of the optimal solution is \(\operatorname {OPT}=\operatorname {cost}\left(e_{i^{*}}\right)\).
Consider a vertex-weighted graph \(H\), and let \(I\) be an independent set in the graph \(H^{2}\). For each \(u \in I\) denote by \(s(u)\) the lightest neighbor of the vertex \(u\) in the graph \(H\) (a vertex \(u\) is also considered its own neighbor). Let \(S=\{ s(u) \mid u \in I\}\).
In the HochbaumβShmoys-2 algorithm, \(s_{i}(u)\) denotes the lightest neighbor of the vertex \(u\) in the graph \(G_{i}\).
A tight example for the 3-approximation of Hochbaum-Shmoys-2
A path \(a\text{-}b\text{-}c\text{-}d\) with unit edges, vertex weights \(a{:}1,\ b{:}2,\ c{:}2,\ d{:}2\), and \(n\) infinite-weight vertices, each joined to \(a\) by an edge of cost \(1+\varepsilon\) (all other distances are shortest paths). For \(W=3\), compare the optimum with what the algorithm can output.