Approximationsalgorithmen für topologisches Netzwerkdesign in Theorie und Praxis
Final Report Abstract
In dem Projekt untersuchten wir topologische Netzwerkdesignprobleme wie z. B. das Steinerbaum-Problem in Graphen. Dabei beschäftigten wir uns einerseits mit Approximationsalgorithmen und deren praktischer Umsetzung, andererseits auch mit der Anwendbarkeit von ähnlichen Konzepten in verwandten Gebieten wie z. B. der Bio- und Geoinformatik. Hauptaspekt der Untersuchungen war die Praktikabilität von den stärksten Approximationsalgorithmen für das Steinerbaum-Problem. Diese wurden vorher ausschließlich unter theoretischen Gesichtspunkten untersucht. Die Güten und Laufzeiten dieser Approximationsalgorithmen sind von einer Konstanten k abhängig. Da die konkurrenzfähigen Güten erst bei k → ∞ erreicht werden, stellt sich die Frage, wie diese Algorithmen sich in der Praxis bei kleinen, realistischen Werten für k verhalten, wie groß man dieses k wählen kann, und ob sich die Wahl eines größeren k s überhaupt auch in der Praxis lohnt. Um dies zu ermitteln, wurden im Wesentlichen alle diese Algorithmen implementiert, im Sinne des Algorithm Engineering an diversen Stellen verbessert, und evaluiert. Im ersten Schritt jedes dieser Algorithmen muss man eine Vielzahl sogenannter „k-beschränkter Komponenten“ erzeugen. Dieser Schritt ist schon ein erster Flaschenhals, weshalb hier unterschiedliche Umsetzungsmöglichkeiten evaluiert wurden. Für k = 3 gibt es eine Algorithmusvariante, bei der diese Komponenten erst erzeugt werden, sobald sie benötigt werden. Es stellte sich heraus, dass dieser Algorithmus – interessanterweise einer der ältesten der starken Algorithmen – der einzige war, dessen Laufzeit nicht signifikant zunimmt, der aber trotzdem bessere Lösungen erreicht als die klassischen Approximationen. Für k = 3 haben wir ein bekanntes Ergebnis erweitert und gezeigt, dass man die vorgelagerte Komponentenerzeugung immer mithilfe von Voronoi-Regionen beschleunigen kann, ohne an Güte zu verlieren. Dies gilt unabhängig vom dahintergeschalteten Approximationsalgorithmus. In der Praxis ist diese Komponentenerzeugung die effizienteste. Für k ≥ 4 funktioniert diese Methode nicht mehr ohne Verluste an der Güte von mindestens 9/8. Einer auf dynamischer Programmierung basierender Ansatz ist hier erfolgsversprechender. Generell ließen sich die Fälle für k ≥ 4 erst unter Zuhilfenahme von Preprocessing-Maßnahmen betrachten. Hierbei werden Steinerbaum-Instanzen verkleinert, ohne dass der Wert der Lösung verändert wird. Dafür mussten wir allerdings zunächst einmal untersuchen, wie sich das Preprocessing auf die erreichten Güten auswirkt: die Güten verändern sich in beide Richtungen, im Allgemeinen ist das Anwenden von Preprocessing aber eher gut (allerdings statistisch nicht signifikant) für die Güte die Lösung. Aus Sicht der Laufzeit ist das Anwenden von Preprocessing nie nachteilig. Ein Nebenergebnis war auch, dass sich die Reihenfolge von Preprocessing-Maßnahmen, wenn man sie iteriert anwendet, kaum auf den erreichten Verkleinerungsfaktor auswirkt. Mittels Preprocessing konnten wir nun Vergleiche der Algorithmen bis k = 6 durchführen und somit Stärken und Schwächen der einzelnen Algorithmen ausmachen. Ein überraschendes Ergebnis war, dass Algorithmen, die nur für k = 3 entwickelt und analysiert wurden, bei größeren k nicht schlechter abschneiden als die für k → ∞ entwickelten Algorithmen. Da bei allen Algorithmen die Komponentenerzeugung die Laufzeit dominiert, waren die Laufzeiten auch im selben Rahmen. Ebenso überraschend war, dass – je nachdem wie man sich Praktikabilität definiert – man nun k = 5 bis k = 6 als praktikabel ansehen kann. Im Spannungsfeld zwischen den besten exakten Algorithmen für das Steinerbaumproblem und den besten (Meta)heuristiken (ohne bekannte Güten) sind die starken Approximationsalgorithmen jedoch noch nicht zu empfehlen. Metaheuristiken erreichen – je nach gewählter Iterationsanzahl – in Bruchteilen von Sekunden bis in wenigen Sekunden maßgeblich bessere Ergebnisse als alle Approximationsalgorithmen. Die exakten Algorithmen finden die optimale Lösung im Mittel bereits in weniger Zeit als die Algorithmen für k = 4 ihre Approximation.
Publications
- Contraction-Based Steiner Tree Approximations in Practice. In Proc. of ISAAC 2011, LNCS 7074, 40–49, Springer, 2011
M. Chimani, M. Woste
(See online at https://doi.org/10.1007/978-3-642-25591-5_6) - Improved Steiner Tree Algorithms for Bounded Treewidth. Journal of Discrete Algorithms 16, 67–78, 2012
M. Chimani, P. Mutzel, B. Zey
(See online at https://doi.org/10.1016/j.jda.2012.04.016) - 2-InterConnected Facility Location: Specification, Complexity, and Exact Solutions. In Proc. of INOC 2013, ENDM 41, 21–28, Elsevier, 2013
M. Chimani, M. Kandyba, M. Martens
(See online at https://doi.org/10.1016/j.endm.2013.05.071) - How to Eat a Graph: Computing Selection Sequences for the Continuous Generalization of Road Networks. In Proc. of ACM SIGSPATIAL 2014, 243–252
M. Chimani, T. C. van Dijk, J.-H. Haunert
(See online at https://doi.org/10.1145/2666310.2666414) - Steiner Tree 1.39-Approximation in Practice. In Proc. of MEMICS 2014 (Selected Papers), LNCS 8934, 60–72, 2014
S. Beyer, M. Chimani
(See online at https://doi.org/10.1007/978-3-319-14896-0_6) - Approximating Spanning Trees with Few Branches. Theory of Computing Systems. 56(1), 181–196, 2015
M. Chimani, J. Spoerhase
(See online at https://doi.org/10.1007/s00224-014-9556-6) - Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees. In Proc. of STACS 2015, 238–248, 2015
M. Chimani, J. Spoerhase
(See online at https://doi.org/10.4230/LIPIcs.STACS.2015.238) - Speedy Colorful Subtrees. In Proc. of COCOON 2015, LNCS 9198: 310–322, 2015
W. T. J. White, S. Beyer, K. Dührkop, M. Chimani, S. Böcker
(See online at https://doi.org/10.1007/978-3-319-21398-9_25) - Strong Steiner Tree Approximations in Practice
S. Beyer, M. Chimani
- The Influence of Preprocessing on Steiner Tree Approximations. In Proc. of COCOA 2015, LNCS 9486, 601–616, LNCS, 2015
S. Beyer, M. Chimani
(See online at https://doi.org/10.1007/978-3-319-26626-8_44)
