Approximationsalgorithmen, Teil I Wie effizient können Sie Objekte in eine minimale Anzahl von Boxen packen? Wie gut können Sie Knoten gruppieren, um ein Netzwerk kostengünstig in Komponenten um einige Zentren herum zu unterteilen? Dies sind Beispiele für NP-schwere kombinatorische Optimierungsprobleme. Es ist höchstwahrscheinlich unmöglich, solche Probleme effizient zu lösen. Unser Ziel ist es daher, eine ungefähre Lösung zu finden, die in polynomieller Zeit berechnet werden kann und gleichzeitig nachweisbare Garantien für die Kosten im Vergleich zum Optimum bietet.

Dieser Kurs setzt Kenntnisse aus einem Standard-Grundkurs Algorithmen voraus und legt besonderen Wert auf Algorithmen, die mit Hilfe der linearen Programmierung entworfen werden können, einer beliebten und erstaunlich erfolgreichen Technik in diesem Bereich. In diesem Kurs lernen Sie eine Reihe von Problemen kennen, die zu den Grundlagen der theoretischen Informatik gehören, sowie leistungsstarke Entwurfs- und Analysetechniken. Nach Abschluss des Kurses werden Sie in der Lage sein, bei einem neuen kombinatorischen Optimierungsproblem zu erkennen, ob es einem der wenigen bekannten Grundprobleme nahe kommt, und Sie werden in der Lage sein, Entspannungen für die lineare Programmierung zu entwerfen und randomisierte Rundungen zu verwenden, um zu versuchen, Ihr eigenes Problem zu lösen. Der Kursinhalt und insbesondere die Hausaufgaben sind theoretischer Natur und beinhalten keine Programmieraufgaben. Dies ist der erste Teil eines zweiteiligen Kurses über Approximationsalgorithmen.