Network design problems with bounded distances via shallow-light steiner trees

Autor(en): Chimani, M. 
Spoerhase, J.
Herausgeber: Mayr, E.W.
Ollinger, N.
Stichwörter: Approximation algorithm; Approximation algorithms; Directed graphs, Distance bound; Light weight; Linear approximations; Network design; Network design problems; Shallow-light spanning trees; Spanners; Spanning tree; Steiner trees, Trees (mathematics)
Erscheinungsdatum: 2015
Herausgeber: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Journal: Leibniz International Proceedings in Informatics, LIPIcs
Volumen: 30
Startseite: 238
Seitenende: 248
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|ε))-approximation, where R is the set of 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. © 2015 LIPICS.
Conference of 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 ; Conference Date: 4 March 2015 Through 7 March 2015; Conference Code:111047
ISBN: 9783939897781
ISSN: 18688969
DOI: 10.4230/LIPIcs.STACS.2015.238
Externe URL:

Show full item record

Page view(s)

Last Week
Last month
checked on Apr 18, 2024

Google ScholarTM