We study several old and new algorithms for computing lower and upper bounds for the Steiner problem in networks using dualascent and primal-dual strategies. 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(re logn) 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 ²) without a constant approximation ratio. Furthermore, 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 ² log n).