Approximationsverfahren für das Steinerbaumproblem und verwandte Netzwerkdesignprobleme mit verschiedenen Industrieanwendungen

• Applicant: Professor Dr. Matthias Müller-Hannemann
• Subject Area: Theoretical Computer Science
• Term: from 2006 to 2008
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 26089266

Das Steinerbaumproblem und verwandte Netzwerkdesignprobleme gehören zu den wichtigsten Klassen von kombinatorischen bzw. geometrischen Optimierungsproblemen mit zahlreichen industriellen und wirtschaftlichen Anwendungen, unter anderem im VLSI-Design, in der Standortplanung und bei ad-hoc-Netzwerken. Vom komplexitätstheoretischen Standpunkt her sind diese Problemklassen in der Regel NP-schwer, so dass man versucht, approximative Algorithmen mit möglichst guter Gütegarantie zu entwickeln. Für viele konkrete Teilprobleme sind die bisher bekannten Approximationsverfahren unbefriedigend, weil entweder die Approximationsgüte relativ schwach ist oder die Verfahren aufgrund ihrer Komplexität als nicht praktikabel für typische Anwendungen gelten müssen. Wesentliche Ziele dieses Projektes bestehen darin, verbesserte Approximationsverfahren für ausgewählte Anwendungen zu entwickeln, die praktisch einsetzbar sind und gleichzeitig möglichst gute Gütegarantien liefern. Bei den Anwendungen wollen wir uns konzentrieren auf rektilineare und oktilineare Steinerbäume unter Berücksichtigung von Blockaden, auf die Minimierung des Stromverbrauchs von Inverterbäumen im VLSI-Design, auf Standortplanungsprobleme mit mehreren Hierarchiestufen und auf effizientes Energiemanagement bei asymmetrischen ad-hoc- Netzwerken. Die verbindende Klammer zwischen diesen unterschiedlichen Anwendungen liegt in ähnlicher Methodik bzw. in einem angestrebten Methodentransfer zwischen diesen Problemen.

• DFG Programme: Research Grants