|
Zusammenfassung:
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 vier Problembereiche betrachtet: Netzwerkausbau bei Standortproblemen, Netzwerkmodifikationen bei Schnittproblemen, Netzwerkentwurf in gerichteten Graphen und die Formulierung von generischen Approximationsalgorithmen für ganze Klassen von Mehrkriterienproblemen mit Hilfe eines syntaktischen Rahmens. Die Implementierung grundlegender Techniken der Approximationsverfahren soll darüberhinaus als Basis für eine breit nutzbare Bibliothek dienen. ANDI: Ein LEDA-Erweiterungs-Paket für Approximationsalgorithmen (Englisch) Hans-Christoph Wirth E-Mail: wirth@informatik.uni-wuerzburg.de |