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