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}.