Starke Approximationsalgorithmen für das Steinerbaumproblem und verwandte Probleme

• Antragsteller: Professor Dr. Markus Chimani
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2016 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 317997620

Wir betrachten Approximationsalgorithmen für klassische und praxisrelevante NP-schwere Probleme aus dem Bereich des topologischen Netzwerkdesigns. Der bekannteste Vertreter, neben dem in polynomieller Zeit lösbaren Spannbaumproblem, ist sicherlich das Steinerbaumproblem: gegeben ein gewichteter Graph, finde einen kostenminimalen Baum, der eine Menge von gegebenen Terminalknoten verbindet. Dieses und verwandte Probleme treten in der Praxis in vielen verschiedenen Bereichen auf, beispielsweise dem Ausbau von Telekommunikationsnetzen, dem VLSI-Design, und der Geographie.Die theoretisch starken Approximationsalgorithmen für das Steinerbaumproblem erwiesen sich in der Vergangenheit wegen der verwendeten Kernkonzepte als wenig praxistauglich. Ziel dieses Projekts ist es, diese Konzepte praxistauglicher zu machen, und neue, praxistauglichere Konzepte zu finden, die ähnliche Gütegarantien erlauben.Neben dem klassischen Steinerbaumproblem betrachten wir auch verwandte Probleme, wie 2-zusammenhängendes Netzwerkdesign, Spanner und Steinerbäume auf gerichteten Graphen, sowie anwendungsnahe Probleme aus der Geoinformatik.

• DFG-Verfahren: Sachbeihilfen