Titel:
Komplexität und Approximierbarkeit von NP-harten
Mehrkriterienproblemen beim Netzwerkentwurf
Projektleitung an der Universität Würzburg:
Beteiligte Wissenschaftlerinnen und Wissenschaftler:
Kurzbeschreibung:
Die Gewinnung von Approximationsalgorithmen für NP-harte
Optimierungsprobleme hat gerade wegen ihrer praktischen Relevanz in
den letzten Jahren immer mehr an Bedeutung gewonnen. Ziel unseres
Vorhabens ist der Entwurf und die Analyse effizienter
Approximationsalgorithmen für NP-harte Mehrkriterienprobleme aus dem
Bereich des Netzwerkentwurfs. Es werden folgende Problembereiche
betrachtet: Netzwerkentwurf und Kostenmodelle bei Transport- und
Lokationsproblemen, Netzwerkausbau bei Fluss- und Schnittproblemen,
Netzwerkausbau bei der Tourenplanung. Ausgewählte Algorithmen werden
implementiert, um die theoretischen Ergebnisse in der Praxis zu
verifizieren.
Laufzeit: von 09.1997 bis 08.2000
Förderinstitution:
DFG