Detailansicht
Entwicklung und Analyse von approximativen Algorithmen für Gemischte und Verallgemeinerte Packungs- und Überdeckungsprobleme
Während der letzten 10 Jahre ist eine neue Forschungsrichtung entstanden mit dem Ziel beweisbar gute approximative Algorithmen für Klassen von linearen und konvexen Optimierungsproblemen zu entwickeln. Zwei wichtige Klassen bilden reine Packungs- und Überdeckungsprobleme über einer konvexen Menge, für die effiziente approximative Algorithmen von Grigoriadis und Khachiyan entwickelt worden sind. Die Laufzeit der vorgeschlagenen Algorithmen hängt von der Anzahl der Iterationen ab, wobei in jeder Iteration eine Funktion über der konvexen Menge approximiert werden muss. Solch eine Approximation ist in vielen Anwendungen effizient möglich. Die Anzahl der Iterationen hängt nur von der Anzahl der Nebenbedingungen und der Genauigkeit ab. Für andere Klassen wie gemischte und verallgemeinerte Packungs- und Überdeckungsprobleme ist die Situation schlechter. Die bisher bekannten Algorithmen benötigen eine Anzahl von Iterationen, die (neben der Anzahl der Nebenbedingungen und der Genauigkeit) zusätzlich von den Eingabedaten (z.B. den Koeffizienten der linearen oder konvexen Funktionen) abhängt. Unser Projektziel ist die Entwicklung und Analyse von approximativen Algorithmen zur effizienten Lösung von gemischten und verallgemeinerten Packungs- und Überdeckungsproblemen, wo diese zusätzliche Abhängigkeit in der Anzahl der Iterationen vermieden wird.
Website:
Keine Website angegeben.
DFG-Verfahren:
Einzelförderung
Antragsteller:
Professor Dr. Klaus Jansen
Christian-Albrechts-Universität zu Kiel
Technische Fakultät
Institut für Informatik
24098 Kiel
Telefon: +49 431 8807501
Telefax: +49 431 880-7614
E-Mail: kj
informatik.uni-kiel.de
Fachliche Zuordnung:
- Theoretische Informatik
Internationaler Bezug:
USA
Förderung:
Förderung seit 2003
verfahrenstechnischer DFG-Ansprechpartner:
