Algorithmic Approaches to the Steiner Problem in Networks

Vorschau

PDF
dissertationVahdati.pdf - Veröffentlichte Version
Download (1MB)

URL:	https://ub-madoc.bib.uni-mannheim.de/176
URN:	urn:nbn:de:bsz:180-madoc-1769
Dokumenttyp:	Dissertation
Erscheinungsjahr:	2004
Titel einer Zeitschrift oder einer Reihe:	None
Verlag:	Universität Mannheim
Gutachter:	Krause, Matthias
Datum der mündl. Prüfung:	23 Februar 2004
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Theoretische Informatik (Krause 1996-)
Fachgebiet:	004 Informatik
Fachklassifikation:	CCS: Linear pro Algorithm Combinator Trees Network pr ,
Normierte Schlagwörter (SWD):	Netzwerk , Algorithmentheorie
Freie Schlagwörter (Deutsch):	Steinerproblem , Relaxationen , Reduktionen , Heuristiken , Exakte Algorithmen
Freie Schlagwörter (Englisch):	Steiner problem , Relaxations , Reductions , Heuristics , Exact algorithms
Abstract:	Das Steinerproblem in Netzwerken ist das Problem, in einem gewichteten Graphen eine gegebene Menge von Knoten kostenminimal zu verbinden. Es ist ein klassisches NP-schweres Problem und ein fundamentales Problem bei der Netzwerkoptimierung mit vielen praktischen Anwendungen. Wir nehmen dieses Problem mit verschiedenen Mitteln in Angriff: Relaxationen, die die Zulässigkeitsbedingungen lockern, um eine optimale Lösung annähern zu können; Heuristiken, um gute, aber nicht garantiert optimale Lösungen zu finden; und Reduktionen, um die Probleminstanzen zu vereinfachen, ohne eine optimale Lösung zu zerstören. In allen Fällen untersuchen und verbessern wir bestehende Methoden, stellen neue vor und evaluieren sie experimentell. Wir integrieren diese Bausteine in einen exakten Algorithmus, der den Stand der Algorithmik für die optimale Lösung dieses Problems darstellt. Viele der vorgestellten Methoden können auch für verwandte Probleme von Nutzen sein.
Übersetzter Titel:	Algorithmische Ansaetze für das Steinerproblem in Netzwerken (Englisch)
Übersetzung des Abstracts:	The Steiner problem in networks is the problem of connecting a set of required vertices in a weighted graph at minimum cost. This is a classical NP-hard problem and a fundamental problem in network design with many practical applications. We approach this problem by different means: Relaxations, which relax the feasibility constraints, to get close to an optimal solution; heuristics to find good, but not necessarily optimal solutions; and reductions to simplify problem instances without abandoning the optimal solution. In each case, we study and improve existing methods, introduce new ones, and evaluate them experimentally. We integrate these components into an exact algorithm, which represents the state of the art for the optimal solution of this problem. Many of the presented methods could also be useful for similar problems. (Englisch)
Zusätzliche Informationen: