0
$\begingroup$

If I must connect: $$2^k$$ terminals in a Steiner Tree choosen randomly and connect them with the cheapest component; "loss - contracting algorithm" is a good way? Or is an "Iterative Randomized Rounding" more appropriate? At the end the cost of minimum spanning tree should be: $$c(T)<=1+(1/k)$$

Thanks

$\endgroup$
  • $\begingroup$ Why was this downvoted? It's a good question. (At least, once it's corrected by multiplying the rhs of the equation by the cost of the Steiner tree.) $\endgroup$ – Peter Shor Dec 28 '14 at 13:22
  • $\begingroup$ Are you talking about directed component cut relaxation? $\endgroup$ – Paul Dec 28 '14 at 13:34

Your Answer

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

Browse other questions tagged or ask your own question.