Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

Primal-Dual Approaches to the Steiner Problem


Polzin,  Tobias
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Polzin, T., & Vahdati Daneshmand, S. (2000). Primal-Dual Approaches to the Steiner Problem. In K. Jansen, & S. Khuller (Eds.), Approximation Algorithms for Combinatorial Optimization (pp. 214-225). Berlin, Germany: Springer.

Cite as:
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)$.