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

• Antragsteller: Professor Dr. Hartmut Noltemeier
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 1997 bis 2001
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren: Sachbeihilfen