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

In a directed graph G with non-correlated edge lengths and costs, the 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 + E, 0(n 5+')) -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 + E. In the course of proving this result, the related problem of 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+E, 0 (1R1E))-approximation, where R is the set of terminals Finally, we show how to apply our results to obtain an (ce E, 0(n 5 -1) -approximation for light-weight directed ce-spanners. For this, no non-trivial approximation algorithm has been known before. All running times depends on n and E and are polynomial in n for any fixed E > 0.