License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.19
URN: urn:nbn:de:0030-drops-188443
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18844/
Go to the corresponding LIPIcs Volume Portal

Foos, Josefine ; Held, Stephan ; Spitzley, Yannik Kyle Dustin

Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem

pdf-format:
LIPIcs-APPROX19.pdf (0.8 MB)

Abstract

Uniform cost-distance Steiner trees minimize the sum of the total length and weighted path lengths from a dedicated root to the other terminals. They are applied when the tree is intended for signal transmission, e.g. in chip design or telecommunication networks. They are a special case of general cost-distance Steiner trees, where different distance functions are used for total length and path lengths.
We improve the best published approximation factor for the uniform cost-distance Steiner tree problem from 2.39 [Khazraei and Held, 2021] to 2.05. If we can approximate the minimum-length Steiner tree problem arbitrarily well, our algorithm achieves an approximation factor arbitrarily close to 1+1/√2. This bound is tight in the following sense. We also prove the gap 1+1/√2 between optimum solutions and the lower bound which we and all previous approximation algorithms for this problem use.
Similarly to previous approaches, we start with an approximate minimum-length Steiner tree and split it into subtrees that are later re-connected. To improve the approximation factor, we split it into components more carefully, taking the cost structure into account, and we significantly enhance the analysis.

BibTeX - Entry

@InProceedings{foos_et_al:LIPIcs.APPROX/RANDOM.2023.19,
  author =	{Foos, Josefine and Held, Stephan and Spitzley, Yannik Kyle Dustin},
  title =	{{Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18844},
  URN =		{urn:nbn:de:0030-drops-188443},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.19},
  annote =	{Keywords: cost-distance Steiner tree, approximation algorithm, uniform}
}

Keywords: cost-distance Steiner tree, approximation algorithm, uniform
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Issue Date: 2023
Date of publication: 04.09.2023

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