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


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