Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913965329612800 |
|---|---|
| author | Foos, Josefine Held, Stephan Spitzley, Yannik Kyle Dustin |
| author_facet | Foos, Josefine Held, Stephan Spitzley, Yannik Kyle Dustin |
| contents | 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 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 + \frac{1}{\sqrt{2}} $. This bound is tight in the following sense. We also prove the gap $ 1 + \frac{1}{\sqrt{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_03381 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem Foos, Josefine Held, Stephan Spitzley, Yannik Kyle Dustin Data Structures and Algorithms 90C27, 68W25, 68M10 G.2.1; G.2.2; F.2.2; B.7.2 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 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 + \frac{1}{\sqrt{2}} $. This bound is tight in the following sense. We also prove the gap $ 1 + \frac{1}{\sqrt{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. |
| title | Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem |
| topic | Data Structures and Algorithms 90C27, 68W25, 68M10 G.2.1; G.2.2; F.2.2; B.7.2 |
| url | https://arxiv.org/abs/2305.03381 |