Problem

Let G=⟨V,E⟩G = \langle V, E \rangle be an undirected and complete graph, with a distance d(v,u)∈R+d(v, u) \in \mathbb{R}^+ between each pair of v,u∈Vv, u \in V. Assume that

  • d(v,v)=0d(v, v) = 0 for each v∈Vv \in V;
  • d(v,u)=d(u,v)d(v, u) = d(u, v) for each v,u∈Vv, u \in V;
  • The distances satisfy triangle inequality:
d(v,w)≤d(v,u)+d(u,w),∀v,u,w∈V. d(v, w) \le d(v, u) + d(u, w), \qquad \forall v, u, w \in V.

The goal is to find a set S⊂VS \subset V with size ∣S∣=k|S| = k, for given input parameter k∈Nk \in \mathbb{N}, to minimize

max⁡v∈Vd(v,S), \max_{v \in V} d(v, S),

where d(v,S)≐min⁡j∈Sd(v,u)d(v, S) \doteq \min_{j \in S} d(v, u) is the distance between ii and its nearest point in SS.

Approximation Algorithm

Algorithm A\mathcal{A}

  1. Pick arbitrary point v1v_1 from VV
  2. S←{v1}S \leftarrow \{ v_1 \}
  3. For t←2t \leftarrow 2 to kk do
  4. \qquad let vt≐arg⁡max⁡v∈V d(v,S)v_t \doteq \underset{v \in V}{\arg \max} \, d(v, S)
  5. \qquad S←S∪{vt}S \leftarrow S \cup \{ v_t \}

Denote the optimal solution as S∗≐{v1∗,…,vk∗}S^* \doteq \{ v_1^*, \ldots, v_k^* \}:

S∗≐arg⁡min⁡S⊆V,∣S∣=k  (max⁡v∈Vd(v,S)). S^* \doteq \underset{S \subseteq V, |S| = k}{\arg \min} \, \, \left( \max_{v \in V} d(v, S) \right).

We claim that the algorithm outputs a 22-approximate solution to S∗S^*.

Theorem. Algorithm A\mathcal{A} outputs a 22-approximate solution:

max⁡v∈Vd(v,S)≤2⋅max⁡v∈Vd(v,S∗). \max_{v \in V} d(v, S) \le 2 \cdot \max_{v \in V} d(v, S^*).

Proof. We can partition the vertices in VV into kk subsets V1∗,…Vk∗V_1^*, \ldots V_k^*, such that

Vi∗≐{v∈V:arg⁡min⁡v∗∈S∗ d(v,v∗)=vi∗},∀i∈[k]. V_i^* \doteq \left\{ v \in V: \underset{v^* \in S^*}{\arg \min} \, d(v, v^*) = v_i^* \right\}, \qquad \forall i \in [k].

Lemma. If u,wu, w belongs to the same subset Vi∗V_i^*, then

d(u,w)≤d(u,vi∗)+d(vi∗,w)≤2⋅max⁡v∈Vd(v,S∗). d(u, w) \le d(u, v_i^*) + d(v_i^*, w) \le 2 \cdot \max_{v \in V} d(v, S^*).

We consider the following two cases:

Case One. For each i∈[k]i \in [k], ∣Vi∗∩S∣=1|V_i^* \cap S| = 1. Fix an i∈[k]i \in [k], and let vt∈Vi∗∩Sv_t \in V_i^* \cap S. Then for each u∈Vi∗u \in V_i^*, via the lemma,

d(u,S)≤d(u,vt)≤2⋅max⁡v∈Vd(v,S∗). d(u, S) \le d(u, v_t) \le 2 \cdot \max_{v \in V} d(v, S^*).

Since Vi∗,i∈[k]V_i^*, i \in [k] is a partition of VV, this holds for all u∈Vu \in V.

Case Two. There exists some Vi∗V_i^* contains more than one points in SS. This implies that at some iteration, the algorithm A\mathcal{A} selects a point vt∈Vi∗v_t \in V_i^*, even though it has selected a point vt′∈Vi∗v_t' \in V_i^* in an earlier iteration.

When vtv_t is selected, via the lemma, it holds that

d(vt,S)≤d(vt,vt′)≤2⋅max⁡v∈Vd(v,S∗). d(v_t, S) \le d(v_t, v_t') \le 2 \cdot \max_{v \in V} d(v, S^*).

Since vtv_t is the farthest point from SS when it is selected, all points are within a distance of 2⋅max⁡v∈Vd(v,S∗)2 \cdot \max_{v \in V} d(v, S^*) from SS. This remains true as the algorithm A\mathcal{A} adds more points.

□\square

Reference

[1] D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms. Cambridge: Cambridge University Press, 2011.