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