Strong Approximation Algorithms for the Steiner Tree Problem and Related Problems
Final Report Abstract
Die beiden Hauptresultate des Projekts lassen sich wie folgt zusammenfassen. Eine frühere Journalpublikation – obgleich schon vor Projektanfang begonnen – begleitete uns einen Gutteil der Projektlaufzeit. Zahlreiche (auch zeitaufwendige) Verbesserungen, Implementationen und Evaluationen fanden hier ihren Niederschlag. Es ist die einzige umfassende Studie zur Praktikabilität von starken Approximationsalgorithmen für das Steinerbaum-Problem. Nicht nur, dass sie in ihrer jetzigen Form viele vormals offene Fragen zur Thematik beantwortet, liefern die vollständigen frei verfügbaren Implementierungen eine Basis für zukünftige Forschungen, und dient als Einladung, nun mit vergleichsweise wenig Aufwand in Zukunft zu entwickelnde Steinerbaum-Approximationen f ür das Problem auch praktisch zu evaluieren. Das zweite Hauptergebnis befasst sich mir der Suche nach einem Approximationsalgorithmus für das 2ECSS Problem, d.h. um in einem kantengewichteten Graphen einen minimalen 2-kantenzusammenhängenden spannenden Teilgraphen zu finden. Nachdem unsere anfängliche Idee (Übertragen der Komponenten-Idee von den Approximationsalgorithmen des Steinerbaum- Problems) nicht funktionierte, begaben wir uns auf eine lange Reise durch verschiedenste Ansätze und Techniken von Approximationsalgorithmen, wovon die meisten zunächst zwar Erfahrung, aber wenige verwertbare Ergebnisse brachten. Am Ende entwickelten wir jedoch einen einfachen und natürlichen Approximationsalgorithmus, der auf der primal-dualen Methode basiert. Während der Algorithmus selbst sehr einfach ist, stellte sich der Gütebeweis als außerordentlich komplex und diffizil heraus. Wir erzielen mit dem Algorithmus zwar nicht die Güte der besten bekannten Ansätze, jedoch den selben Faktor wie die besten bekannten – und deutlich komplizierteren – anderen primal-dualen Algorithmen. Der wesentliche Aspekt des Resultats sind die algorithmische Einfachheit sowie die neue Methodik, da wir zum ersten mal mit einem nur einstufigen Prozess unsere Lösung ermitteln können.
Publications
- A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs
S. Beyer, M. Chimani, J. Spoerhase
- Strong Steiner Tree Approximations in Practice. Journal of Experimental Algorithmics (JEA), Volume 24 Issue 2, 2019
S. Beyer, M. Chimani
(See online at https://doi.org/10.1145/3299903)
