Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees

Abstract

In a directed graph $G$ with non-correlated edge lengths and costs, the \emph{network design problem with bounded distances} asks for a cost-minimal spanning subgraph subject to a length bound for all node pairs. We give a bi-criteria $(2+\epsilon ,O(n^{0.5+\epsilon }))$-approximation for this problem. This improves on the currently best known linear approximation bound, at the cost of violating the distance bound by a factor of at most~$2+\epsilon$. In the course of proving this result, the related problem of \emph{directed shallow-light Steiner trees} arises as a subproblem. In the context of directed graphs, approximations to this problem have been elusive. We present the first non-trivial result by proposing a $(1+\epsilon ,O(|R{|}^{\epsilon }))$-ap\-proxi\-ma\-tion, where $R$ are the terminals. Finally, we show how to apply our results to obtain an $(\alpha +\epsilon ,O(n^{0.5+\epsilon }))$-approximation for \emph{light-weight directed $\alpha$-spanners}. For this, no non-trivial approximation algorithm has been known before. All running times depends on $n$ and $\epsilon$ and are polynomial in $n$ for any fixed $\epsilon >0$.