## 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 |

Zusammenfassung: | 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. |

Beschreibung: | 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: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84923910486&doi=10.4230%2fLIPIcs.STACS.2015.238&partnerID=40&md5=f442a6a9669db45da2193dc26ee8cf31 |

Show full item record