Approximationsalgorithmen Teil I | Das Universitätsnetzwerk

Beschreibung

Approximationsalgorithmen, Teil I.

Wie effizient können Sie Objekte in eine Mindestanzahl von Kartons packen? Wie gut können Sie Knoten gruppieren, um ein Netzwerk kostengünstig in Komponenten um einige Zentren herum aufzuteilen? Dies sind Beispiele für NP-harte 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 Polynomzeit berechnet werden kann und gleichzeitig nachweisbare Garantien für ihre Kosten im Verhältnis zum Optimum aufweist.

Dieser Kurs setzt Kenntnisse eines Standardkurses für Algorithmen für Studenten voraus und hebt insbesondere Algorithmen hervor, die mit linearer Programmierung entworfen werden können, einer bevorzugten und erstaunlich erfolgreichen Technik in diesem Bereich. Wenn Sie diesen Kurs belegen, werden Sie mit einer Reihe von Problemen auf den Grundlagen der theoretischen Informatik sowie mit leistungsstarken Entwurfs- und Analysetechniken konfrontiert. Nach Abschluss des Vorgangs können Sie bei einem neuen kombinatorischen Optimierungsproblem erkennen, ob es einem der wenigen bekannten Grundprobleme nahe kommt, und Sie können lineare Programmierrelaxationen entwerfen und mithilfe einer zufälligen Rundung versuchen, Ihr Problem zu lösen eigenes Problem. Der Kursinhalt und insbesondere die Hausaufgaben sind theoretischer Natur ohne Programmieraufgaben.

Dies ist der erste Teil eines zweiteiligen Kurses über Approximationsalgorithmen.