DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.19

Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem

Authors: Josefine Foos, Stephan Held, and Yannik Kyle Dustin Spitzley

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

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.

Cite as

Josefine Foos, Stephan Held, and Yannik Kyle Dustin Spitzley. Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.19},
  URN =		{urn:nbn:de:0030-drops-188443},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.19},
  annote =	{Keywords: cost-distance Steiner tree, approximation algorithm, uniform}
}

Search Results

Documents authored by Spitzley, Yannik Kyle Dustin

Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message