We study several old and new algerithms 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(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 empiricalbounds has running time O(e²) 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² log n). The presented insights can also behelpful for the development of further relaxation based approximation algorithms for the Steiner problem.
Zusätzliche Informationen:
Dieser Eintrag ist Teil der Universitätsbibliographie.
Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)
Suche Autoren in