# Greedy algorithm for a variation of the $k$-center problem

This is a variation of the well-known $$k$$-center problem with priorities given on the vertices.

Problem:

Let $$G = (V,E)$$ be a complete graph with a distances on the edges satisfying the triangle inequality. Then, additionally, there is a priority function $$p: V\to (0,\infty)$$. Given some $$k\in\mathbb{N}$$ then we wish to solve the following optimization problem $$\min_{\substack{C \subseteq V \\ |C|\leq k}} \text{cost}(C)$$ where the cost is given by $$\text{cost}(C) = \max_{v\in V}p(v)\cdot d(v,C)$$ and $$d(v,C)$$ is the distance from $$v$$ to its closest center $$c\in C$$.

Assume that we know the optimal radius $$r^*$$. Then we propose the following greedy algoritm:

1. Initialize $$S = V$$ and $$C = \emptyset$$.
2. Now repeat steps $$3$$-$$5$$ as long as $$S \neq \emptyset$$:
3. Select the vertex $$c\in S$$ with the highest priority $$p(c)$$.
4. Add $$c$$ to $$C$$, i.e. $$C := C \cup \{c\}$$.
5. Remove all vertices $$v$$ from $$S$$ that satisfies $$p(v)\cdot d(v,c) \leq 2r^*$$
6. Return $$C$$.

I wish to prove that this is a $$2$$-approximation algorithm. I'm having trouble specifically to get the $$2$$-factor. I've looked at some proofs of the usual $$k$$-center problem algorithms for inspiration, but the priority part is throwing me off.

Can anyone give a proof of the $$2$$-factor, or perhaps some hints?

As a hint, let me work out the case $k = 1$ for you. We are given that some set $C$ of size 1 satisfies $p(v) d(v,C) \leq r^*$ for all $v \in V$. Let $C = \{x\}$. Then $p(v) d(v,x) \leq r^*$ for all $v \in V$.

The given algorithm picks the point $c$ which maximizes $p(c)$, and then removes from $S$ all points in $A = \{ v \in V : p(v) d(v,c) \leq 2r^* \}$. We will show that $A = V$, and so the algorithm terminates after one step, outputting the set $C = \{c\}$. By construction, $p(v)d(v,c) \leq 2r^*$ for all $v \in V$, so this is a 2-approximation.

It remains to show that $A = V$, that is, that all vertices $v \in V$ satisfy $p(v) d(v,c) \leq 2r^*$. Indeed, since $p(v) d(v,x), p(c) d(c,x) \leq r^*$, the triangle inequality implies that $$p(v) d(v,c) \leq p(v) d(v,x) + p(v) d(c,x) \leq p(v) d(v,x) + p(c) d(c,x) \leq 2r^*,$$ using the obvious $p(v) \leq p(c)$.

All that remains is to generalize this proof for larger $k$.

• Thanks a lot for the answer, +1. By the set $C$ you specifically mean the set generated from the optimal solution and not the approximate one, right?
– Eff
Aug 11 '16 at 20:10
• I mean both. In the first paragraph it is the optimal solution, in the second it is the approximate one. Aug 11 '16 at 20:13
• Yes, thank you, it was the first I meant. I'll try and solve the problem with your help! :)
– Eff
Aug 11 '16 at 20:13