License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.238
URN: urn:nbn:de:0030-drops-49170
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4917/
Go to the corresponding LIPIcs Volume Portal

Chimani, Markus ; Spoerhase, Joachim

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

pdf-format:
17.pdf (0.6 MB)

Abstract

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+\varepsilon,O(n^{0.5+\varepsilon}))-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+\varepsilon.

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+\varepsilon,O(|R|^{\varepsilon}))-ap\-proximation, where R is the set of terminals.

Finally, we show how to apply our results to obtain an (\alpha+\varepsilon,O(n^{0.5+\varepsilon}))-approximation for light-weight directed \alpha-spanners. For this, no non-trivial approximation algorithm has been known before. All running times depends on n and
\varepsilon and are polynomial in n for any fixed \varepsilon>0.

BibTeX - Entry

@InProceedings{chimani_et_al:LIPIcs:2015:4917,
  author =	{Markus Chimani and Joachim Spoerhase},
  title =	{{Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{238--248},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4917},
  URN =		{urn:nbn:de:0030-drops-49170},
  doi =		{10.4230/LIPIcs.STACS.2015.238},
  annote =	{Keywords: network design, approximation algorithm, shallow-light spanning trees, spanners}
}

Keywords: network design, approximation algorithm, shallow-light spanning trees, spanners
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI