  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.

Data Structures and Algorithms