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
on the edges of $G$, a buy cost $b:E\longrightarrow \RR^+$ and a rent
cost $r:E\longrightarrow \RR^+$. The goal is to find a subtree $H$ of
$G$ rooted at $s$ with at least $k$ terminals so that the cost
$\sum_{e\in H} b(e)+\sum_{t\in T-s} dist(t,s)$ is minimize, where
$dist(t,s)$ is the distance from $t$ to $s$ in $H$ with respect to
the $r$ cost. Our main result is an $O(\log^5 n)$-approximation for
the buy-at-bulk $k$-Steiner tree problem.
To achieve this we also design an approximation algorithm for
bicriteria $k$-Steiner tree. In the bicriteria $k$-Steiner tree problem we
are given a graph $G$ with edge costs $b(e)$ and distance costs
$r(e)$ over the edges, and an integer $k$. Our goal is to find a
minimum cost (under $b$-cost) $k$-Steiner tree such that the
diameter under $r$-cost is at most some given bound $D$. An
$(\alpha,\beta)$-approximation finds a subgraph of diameter at most
$\alpha\cdot {D}$ (with respect to $r$) and cost with respect to
$b$ of at most $\beta\cdot opt$ where $opt$ is the minimum cost of
any solution with diameter at most $D$. Marathe et al \cite{ravi}
gave an $(O(\log n),O(\log n))$-approximation algorithm for the
bicriteria Steiner tree problem. Their algorithm does not extend to
the bicriteria $k$-Steiner tree problem.
Our algorithm for the buy-at-bulk $k$-Steiner tree problem relies on an
$(O(\log^2 n),O(\log^4 n))$-approximation algorithm we develop for the
(shallow-light) bicriteria $k$-Steiner tree problem, which is of
independent interest. Indeed, this is also one of the main tools we use to obtain
the first polylogarithmic approximation algorithm for non-uniform
multicommodity buy-at-bulk~\cite{HKS}.