Primal-dual approaches to the Steiner problem


Polzin, Tobias ; Vahdati Daneshmand, Siavash


[img]
Preview
PDF
2000_14.pdf - Published

Download (1MB)

URL: https://ub-madoc.bib.uni-mannheim.de/1842
URN: urn:nbn:de:bsz:180-madoc-18428
Document Type: Working paper
Year of publication: 2000
Publication language: English
Institution: School of Business Informatics and Mathematics > Sonstige - Fakultät für Mathematik und Informatik
MADOC publication series: Veröffentlichungen der Fakultät für Mathematik und Informatik > Institut für Informatik > Technical Reports
Subject: 004 Computer science, internet
Classification: MSC: 68Q17 68W25 90C27 ,
Subject headings (SWD): Steiner-Problem , Relaxation , Untere Schranke , Approximationsalgorithmus
Keywords (English): Steiner problem , relaxation , lower bound , approximation algorithms , dual-ascent , primal-dual
Abstract: 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.
Additional information:

Dieser Eintrag ist Teil der Universitätsbibliographie.

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.




+ Citation Example and Export

Polzin, Tobias ; Vahdati Daneshmand, Siavash (2000) Primal-dual approaches to the Steiner problem. Open Access [Working paper]
[img]
Preview


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item