2014/09/23 by Chimani, Markus, Spoerhase, Joachim · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1409.6551
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+ε,O(n0.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+ε. 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+ε,O(|R|ε))-ap\-proxi\-ma\-tion, where R are the terminals. Finally, we show how to apply our results to obtain an (α+ε,O(n0.5+ε))-approximation for light-weight directed α-spanners. For this, no non-trivial approximation algorithm has been known before. All running times depends on n and ε and are polynomial in n for any fixed ε>0.