Approximationsverfahren für das Steinerbaumproblem und verwandte Netzwerkdesignprobleme mit verschiedenen Industrieanwendungen
Final Report Abstract
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.
Publications
-
A near linear time approximation scheme for Steiner tree among obstacles in the plane, 10th Workshop on Algorithms and Data Structures (WADS 2007), Lecture Notes in Computer Science, vol. 4619, Springer, 2007, pp. 151-162
Matthias Müller-Hannemann and Siamak Tazari
-
Hardness and approximation of octilinear Steiner trees, International Journal on Computational Geometry and Applications (IJCGA) 17 (2007), 231-260
Matthias Müller-Hannemann and Anna Schulze
-
A faster shortest-paths algorithm for minor-closed graph classes, WG '08: Proceedings of the 34th Workshop on Graph Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 5344, Springer, 2008, pp. 360-371
Siamak Tazari and Matthias Müller-Hannemann
-
Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation, Discrete Applied Mathematics (2008)
Siamak Tazari and Matthias Müller-Hannemann
-
Dealing with large hidden constants: Engineering a planar Steiner tree PTAS, ALENEX '09: Proceedings of the 11th Workshop on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, Philadelphia, 2009, pp. 120-131
Siamak Tazari and Matthias Müller-Hannemann
