Algorithmische Behandlung schwerer Optimierungsprobleme in Netzwerken

• Applicant: Professor Dr. Matthias Krause
• Subject Area: Theoretical Computer Science
• Term: from 2001 to 2006
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5320258

Ein zentrales Problem in Netzwerken besteht darin, Verbindungsstrukturen zu finden, die gewisse Kriterien erfüllen. Der Kern dieses Problems wird durch das Steiner-Problem in Netzwerken modelliert, also das Problem, eine gegebene Menge von Knoten in einem gewichteten Graphen möglichst kostengünstig zu verbinden. Aufbauend auf der erfolgreichen Arbeit über das Steiner-Problem werden in dem Projekt folgende Ziele verfolgt: 1. Vertiefung des strukturellen Wissens über das Steiner-Problem, seine Relaxationen und die damit verbundenen Bearbeitungsmethoden, 2. Entwicklung eines auf Interior-Point Methoden basierenden Algorithmus für große Instanzen des Steiner-Problems. Diese Zusammenführung von Fortschritten bei Linearer und Kombinatorischer Optimierung stellt eine methodische Innovation dar, die zudem die Möglichkeit einer effizienten verteilten (parallelen) Implementierung beinhaltet. 3. Adaption der beim Steiner-Problem erfolgreichen Methoden auf verwandte schwere Optimierungsprobleme, insbesondere die durch die Anwendungen motivierten Mehrkriterienprobleme wie gradbeschränkte Steiner- und Spannbäume.

• DFG Programme: Priority Programmes
• Subproject of: SPP 1126: Algorithmics of Large and Complex Networks