4
$\begingroup$

I'm reading about the prize collecting steiner tree problem and an approximation algorithm that uses randomization to set a lower bound on the optimal solution (see Chapter 5.7 in The Design of Approximation Algorithms by Williamson and Shmoys). I don't understand the second line in the proof for Lemma 5.16: Lemma 5.16.

It seems to me that $V-V(T)$ is a much larger set than $U$. So, how can the total penalty for this set be upper bounded by the total penalty of a set that is much smaller?

$\endgroup$

migrated from stackoverflow.com Apr 6 '13 at 0:36

This question came from our site for professional and enthusiast programmers.

4
$\begingroup$

$T$ is a tree that connects the chosen subset of terminals $U$. Thus $U$ is a subset of $V(T)$, and $V \setminus V(T)$ is a subset of $V \setminus U$ (we're summing $i$ not in $U$).

$\endgroup$

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.