Approximation algorithms for mixed and generalized packing and covering problems

点击翻译按钮获取中文摘要

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.