Primal-dual approaches to the Steiner problem


Polzin, Tobias ; Vahdati Daneshmand, Siavash


[img]
Vorschau
PDF
2000_14.pdf - Veröffentlichte Version

Download (1MB)

URL: https://ub-madoc.bib.uni-mannheim.de/1842
URN: urn:nbn:de:bsz:180-madoc-18428
Dokumenttyp: Arbeitspapier
Erscheinungsjahr: 2000
Sprache der Veröffentlichung: Englisch
Einrichtung: Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Sonstige - Fakultät für Mathematik und Informatik
MADOC-Schriftenreihe: Veröffentlichungen der Fakultät für Mathematik und Informatik > Institut für Informatik > Technical Reports
Fachgebiet: 004 Informatik
Fachklassifikation: MSC: 68Q17 68W25 90C27 ,
Normierte Schlagwörter (SWD): Steiner-Problem , Relaxation , Untere Schranke , Approximationsalgorithmus
Freie Schlagwörter (Englisch): 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.
Zusätzliche Informationen:

Dieser Eintrag ist Teil der Universitätsbibliographie.

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




+ Zitationsbeispiel und Export

Polzin, Tobias und Vahdati Daneshmand, Siavash (2000) Primal-dual approaches to the Steiner problem. [Arbeitspapier]
[img]
Vorschau



+ Suche Autoren in

+ Download-Statistik

Downloads im letzten Jahr

Detailierte Angaben



Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail


Actions (login required)

Eintrag anzeigen Eintrag anzeigen