Approximationsalgorithmen Teil II | Das Universitätsnetzwerk

Beschreibung

Approximationsalgorithmen, Teil 2

Dies ist die Fortsetzung der Approximationsalgorithmen, Teil 1. Hier lernen Sie die Dualität der linearen Programmierung, die auf das Design einiger Approximationsalgorithmen angewendet wird, und die semidefinite Programmierung, die auf Maxcut angewendet wird.

Wenn Sie die beiden Teile dieses Kurses belegen, werden Sie einer Reihe von Problemen auf den Grundlagen der theoretischen Informatik sowie leistungsstarken Entwurfs- und Analysetechniken ausgesetzt sein. 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 zweite Teil eines zweiteiligen Kurses über Approximationsalgorithmen.