<p>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)&lt;=1+(1/k)$$</p>

<p>Thanks</p>

CC BY-SA 3.0
2014-12-28T13:22:46.463Z
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.)
Peter Shor 
CC BY-SA 3.0
2014-12-28T13:34:57.817Z
Are you talking about directed component cut relaxation?
Paul
<graph-theory><approximation-algorithms><optimization><randomized-algorithms><tree>
Steiner Tree and minimum spanning tree
Paul
# Steiner Tree and minimum spanning tree

(Asked by: username_0 on 2014-12-28)

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

**Tags:** graph-theory, approximation-algorithms, optimization, randomized-algorithms, tree
> **Comments:**
> **username_1**: 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.)  
> **username_0**: Are you talking about directed component cut relaxation?  

---

## 0 answers

