2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Eff Aug 11 '16 at 20:10
  • $\begingroup$ I mean both. In the first paragraph it is the optimal solution, in the second it is the approximate one. $\endgroup$ – Yuval Filmus Aug 11 '16 at 20:13
  • $\begingroup$ Yes, thank you, it was the first I meant. I'll try and solve the problem with your help! :) $\endgroup$ – Eff Aug 11 '16 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.