A Comparison of Steiner Tree Relaxations


Polzin, Tobias ; Vahdati Daneshmand, Siavash


[img]
Vorschau
PDF
1998_05.pdf - Veröffentlichte Version

Download (974kB)

URL: http://ub-madoc.bib.uni-mannheim.de/1747
URN: urn:nbn:de:bsz:180-madoc-17477
Dokumenttyp: Arbeitspapier
Erscheinungsjahr: 1998
Titel einer Zeitschrift oder einer Reihe: None
Sprache der Veröffentlichung: Englisch
Einrichtung: Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Sonstige - Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik
MADOC-Schriftenreihe: Veröffentlichungen der Fakultät für Mathematik und Informatik > Institut für Informatik > Technical Reports
Fachgebiet: 004 Informatik
Normierte Schlagwörter (SWD): Steiner-Problem , Relaxation , Untere Schranke
Freie Schlagwörter (Englisch): Steiner problem , relaxation , lower bound
Abstract: There are many (mixed) integer programming formulations of the Steiner problem in networks. The corresponding linear programming relaxations are of great interest particularly, but not exclusively, for computing lower bounds; but not much has been known ab out the relative quality of these relaxations. We compare all classical and some new relaxations from a theoretical point of view with respect to their optimal values. Among other things, we prove that the optimal value of a flowclass relaxation (e.g. the multicommodity flow or the dicut relaxation) cannot be worse than the optimal value of a tree-class relaxation (e.g. degree-constrained spanning tree relaxation) and that the ratio of the corresponding optimal values can be arbitrarily large. Furthermore, we present a new flow based relaxation, which is to the authors' knowledge the strongest linear relaxation of polynomial size for the Steiner problem in networks.
Zusätzliche Informationen:




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




Metadaten-Export


Zitation


+ Suche Autoren in

+ Download-Statistik

Downloads im letzten Jahr

Detaillierte Angaben



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


Actions (login required)

Eintrag anzeigen Eintrag anzeigen