Beim Steinerbaumproblem geht es darum, eine vorgegebene Menge von Knoten eines Graphen oder von Punkten in der Ebene (so genannte Terminale) kürzestmöglich zu einem zusammenhängenden Netzwerk zu verbinden. Das Steinerbaumproblem und verwandte Netzwerkdesignprobleme gehören zu den wichtigsten Klassen von kombinatorischen bzw. geometrischen Optimierungsproblemen mit zahlreichen industriellen und wirtschaftlichen Anwendungen, unter anderem im VLSI-Design, in der Standortplanung und bei ad-hoc-Netzwerken. Vom komplexitätstheoretischen Standpunkt her sind diese Problemklassen in der Regel NP-schwer. Wesentliches Ziel dieses Projektes war es, verbesserte Approximationsverfahren in Hinblick auf Effizienz oder Approximationsgüte für ausgewählte Anwendungen zu entwerfen. Außerdem ging es darum, Verfahren zu entwickeln, die nicht nur theoretisch, sondern auch praktisch einsetzbar sind. Folgende Hauptergebnisse wurden erzielt und veröffentlicht: Ein erster Linearzeitalgorithmus für die Approximation von Steinerbäumen in minorenabgeschlossenen Graphenklassen, insbesondere planaren Graphen, mit Gütegarantie Faktor 2 und als Voraussetzung dafür ein erster Linearzeitalgorithmus für Kürzeste-Wege-Probleme auf diesen Graphenklassen ein polynomiales Approximationsschema für geometrische Steinerbaumprobleme mit polygonalen Hindernissen, d.h. mit Gebieten, die nicht zum Verbinden benutzt werden dürfen, das fast in Linearzeit läuft; ein polynomiales Approximationsschema für Graphen mit beschränktem Geschlecht. Die erste Implementation eines sehr komplizierten, ursprünglich als hochgradig praxisfern eingeschätzten polynomialen Approximationsschemas für planare Graphen wurde mit Methoden des Algorithm Engineering durchgeführt. In der Praxis müssen die Parameter des zugehörigen Programms heuristisch kleiner gesetzt werden, als von der Theorie verlangt. Auch wenn dadurch die theoretische Approximationsgarantie verloren geht, erzielen wir Resultate, die viel besser sind als die versprochene Garantie. Mit unserem Programm lassen sich sehr große Testfälle mit mehreren Hundert Terminalen und einer Million Knoten in einer Stunde Rechenzeit behandeln. Bei der energieeffizienten Dimensionierung von ad-hoc-Netzwerken für "broadcasting"-Aufgaben, bei dem von einem Quellknoten aus an alle anderen Knoten des Netzwerkes eine Nachricht geschickt werden soll, konnten mit Hilfe von Methoden der ganzzahligen linearen Programmierung Testfälle mit bis zu 35 Knoten exakt gelöst werden.