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

Question

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?

Answer 1

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