Improved Algorithms for the Steiner Problem in Networks


Polzin, Tobias ; Vahdati Daneshmand, Siavash


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

Download (2MB)

URL: http://ub-madoc.bib.uni-mannheim.de/1748
URN: urn:nbn:de:bsz:180-madoc-17481
Dokumenttyp: Arbeitspapier
Erscheinungsjahr: 1998
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
Normierte Schlagwörter (SWD): Steiner-Problem , Untere Schranke , Heuristik
Freie Schlagwörter (Englisch): Steiner problem , reduction tests , lower bounds , heuristics , exact algorithm
Abstract: We present several new techniques for dealing with the Steiner problem in (undirected) networks. We consider them as building blocks of an exact algorithm, but each of them could also be of interest in its own right. First, we consider some relaxations of integer programming formulations of this problem and investigate different methods for dealing with these relaxations, not only to obtain lower bounds, but also to get additional information which is used in the computation of upper bounds and in reduction techniques. Then, we modify some known reduction tests and introduce some new ones. We integrate some of these tests into a package with a small worst case time which achieves impressive reductions on a wide range of instances. On the side of upper bounds, we introduce the new concept of heuristic reductions. On the basis of this concept, we develop heuristics that achieve sharper upper bounds than the strongest known heuristics for this problem despite running times which are smaller by orders of magnitude. Finally, we integrate these blocks into an exact algorithm. We present computational results on a variety of benchmark instances. The results are clearly superior to those of all other exact algorithms known to the authors.
Zusätzliche Informationen:

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




+ Zitationsbeispiel und Export

Polzin, Tobias und Vahdati Daneshmand, Siavash (1998) Improved Algorithms for the Steiner Problem in Networks. [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