We study several old and new algorithms for computing lower
and upper bounds for the Steiner problem in networks using dual-ascent
and primal-dual strategies. These strategies have been proven to be
very useful for the algorithmic treatment of the Steiner problem. We
show that none of the known algorithms can both generate tight lower
bounds empirically and guarantee their quality theoretically; and we
present a new algorithm which combines both features.
The new algorithm has running time O(r e log n) and guarantees a
ratio of at most two between the generated upper and lower bounds,
whereas the fastest previous algorithm with comparably tight empirical
bounds has running time O(e^2) without a constant approximation ratio.
We show that the approximation ratio two between the bounds can even
be achieved in time O(e + n log n), improving the previous time bound
of O(n^2 log n).
The presented insights can also be helpful for the development of
further relaxation based approximation algorithms for the Steiner
problem.