Approximation Algorithms for Quickest Spanning Tree Problems

Let $G=(V,E)$ be an undirected multigraph with a special vertex ${it root} in V$, and where each edge $e in E$ is endowed with a length $l(e) geq 0$ and a capacity $c(e) > 0$. For a path $P$ that connects $u$ and $v$, the {it transmission time} of $P$ is defined as $t(P)=mbox{large$Sigma$}_{e in P} l(e) + max_{e in P}!{(1 / c(e))}$. For a spanning tree $T$, let $P_{u,v}^T$ be the unique $u$--$v$ path in $T$. The {sc quickest radius spanning tree problem} is to find a spanning tree $T$ of $G$ such that $max _{v in V} t(P^T_{root,v})$ is minimized. In this paper we present a 2-approximation algorithm for this problem, and show that unless $P =NP$, there is no approximation algorithm with a performance guarantee of $2 - epsilon$ for any $epsilon >0$. The {sc quickest diameter spanning tree problem} is to find a spanning tree $T$ of $G$ such that $max_{u,v in V} t(P^T_{u,v})$ is minimized. We present a ${3 over 2}$-approximation to this problem, and prove that unless $P=NP$ there is no approximation algorithm with a performance guarantee of ${3 over 2}-epsilon$ for any $epsilon >0$.