Datensatz

Zusammenfassung

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. 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\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. 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^2\log n)$.