Under the auspices of the Computational Complexity Foundation (CCF)

TR06-007 | 23rd November 2005
#### Approximating Buy-at-Bulk $k$-Steiner trees
In the buy-at-bulk $k$-Steiner tree (or rent-or-buy
$k$-Steiner tree) problem we are given a graph $G(V,E)$ with a set
of terminals $T\subseteq V$ including a particular vertex $s$ called
the root, and an integer $k\leq |T|$. There are two cost functions