Komplexität und Approximierbarkeit von NP-harten Mehrkriterienproblemen beim Netzwerkentwurf

• Applicant: Professor Dr. Hartmut Noltemeier
• Subject Area: Theoretical Computer Science
• Term: from 1997 to 2001
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5366885

Das Projekt beschäftigt sich mit Problemen, wie sie etwa bei der Planung von Telekommunikationsnetzen, Verkehrswegen, Transportplänen, Notfallversorgung o. ä. auftreten. Die Probleme werden dabei durch kanten- und knotenbewertete Graphen modelliert. Sie sind häufig durch mehrere Zielkriterien gekennzeichnet und in der Regel NP-hart. Ziel ist es, Approximationsaussagen zu gewinnen und evtl. generische Approximationsverfahren zu entwickeln. Die gewonnenen Lösungen können dann im konkreten Einzelfall zum Netzwerkentwurf und zur Netwerkoptimierung herangezogen werden. Besonderes Augenmerk finden daher Mehrkriterienprobleme und Ausbauprobleme, bei deren Lösung die bereits vorhandene Infrastruktur berücksichtigt und, soweit möglich, sinnvoll weitergenutzt wird. Auch hier erweist sich der Großteil der Probleme als NP-hart, so daß nach effizienten Verfahren mit garantierter Approximationsgüte gesucht wird, ggf. auch die Nichtapproximierbarkeit nachgewiesen werden soll.

• DFG Programme: Research Grants