Approximation algorithms for mixed and generalized packing and covering problems

• Applicant: Professor Dr. Klaus Jansen
• Subject Area: Theoretical Computer Science
• Term: from 2003 to 2006
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5410280

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.

• DFG Programme: Research Grants