2023/05/05 by Foos, Josefine, Held, Stephan, Spitzley, Yannik Kyle Dustin
#68M10 #68W25 #90C27 #B.7.2 #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.1 #G.2.2
paper · doi:10.48550/arxiv.2305.03381
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 + (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.