TR06-007 Authors: MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour

Publication: 19th January 2006 06:50

Downloads: 4088

Keywords:

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