Approximationsalgorithmen für topologisches Netzwerkdesign in Theorie und Praxis

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

Wir betrachten Approximationsalgorithmen für diverse klassische und praxisrelevante topologische Netzwerkdesignprobleme. Die bisherige einschlägige Forschung hat sich, mit wenigen Ausnahmen, bisher nie mit der praktischen Anwendbarkeit und tatsächlich erzielten Güte dieser Algorithmen beschäftigt. Abgesehen von rein kombinatorischen Algorithmen basieren viele Approximationen auf ungerichteten Formulierungen durch ganzzahlige lineare Programme (ILPs); jedoch haben aktuelle Forschungsergebnisse beweisbar stärkere gerichtete Formulierungen aufgezeigt, die auch das exakte Lösen von nicht zu großen Realinstanzen erlauben. Ziel des Projekts ist es einerseits, diese gerichteten Modelle zur Entwicklung neuer Approximationen zu nutzen, und andererseits die (bekannten und neuen) Approximationsalgorithmen im Kontext der Praxistauglichkeit im experimentellen Vergleich anderen (heuristischen wie exakten) Methoden gegenüberzustellen. Den Prinzipien des Algorithm Engineering folgend, ist es dabei zum einen von besonderem Interesse wie man die vorhandenen Algorithmen für Realinstanzen positiv modifizieren kann. Zum anderen möchten wir untersuchen, welche implementativ komplizierten oder rechenaufwendigen Teilschritte durch simplere Datenstrukturen und Algorithmen ersetzt werden können, ohne der Güte (praktisch und/oder analytisch) zu sehr zu schaden. Insgesamt hoffen wir durch dieses Projekt die in der Regel recht disjunkten Forschungsgebiete der Approximation und des Algorithm Engineering näher aneinander zu bringen.

• DFG-Verfahren: Sachbeihilfen