Die lineare Programmierung ist ein sehr leistungsfähiges algorithmisches Werkzeug. Im Wesentlichen geht es bei einem linearen Programmierproblem darum, eine lineare Funktion reeller Variablen zu optimieren, die durch ein System linearer Ungleichungen eingeschränkt wird. Dies ist ein äußerst vielseitiger Rahmen, der sich sofort auf die Verallgemeinerung von Flussproblemen anwenden lässt, aber auch zur Diskussion einer Vielzahl anderer Probleme verwendet werden kann, von der Optimierung von Produktionsverfahren bis hin zur Suche nach dem billigsten Weg zu einer gesunden Ernährung. Überraschenderweise lässt dieser sehr allgemeine Rahmen effiziente Algorithmen zu. In dieser Lektion werden wir einige der wichtigsten Probleme der linearen Programmierung sowie einige der Werkzeuge zu ihrer Lösung besprechen.

Obwohl viele der Algorithmen, die Sie bisher gelernt haben, in der Praxis häufig angewandt werden, stellt sich heraus, dass die Welt von realen Problemen ohne einen bekannten, nachweislich effizienten Algorithmus dominiert wird. Viele dieser Probleme lassen sich auf eines der klassischen Probleme reduzieren, die als NP-komplette Probleme bezeichnet werden und die entweder nicht durch einen polynomialen Algorithmus gelöst werden können oder deren Lösung Ihnen eine Million Dollar (siehe Millenium Prize Problems) und ewigen Weltruhm für die Lösung des Hauptproblems der Informatik namens P vs NP einbringen würde. Es ist gut, das zu wissen, bevor Sie versuchen, ein Problem vor der morgigen Deadline zu lösen :) Obwohl es sehr unwahrscheinlich ist, dass diese Probleme in naher Zukunft effizient gelöst werden können, lassen sich die Menschen immer wieder verschiedene Umgehungslösungen einfallen. In diesem Modul werden Sie die klassischen NP-kompletten Probleme und die Reduktionen zwischen ihnen studieren. Sie werden auch üben, große Instanzen einiger dieser Probleme trotz ihrer Schwierigkeit zu lösen, indem Sie sehr effiziente Spezialsoftware verwenden, die auf tonnenweise Forschung im Bereich der NP-kompletten Probleme basiert.

Nach dem vorangegangenen Modul sind Sie vielleicht traurig: Sie haben gerade 5 Kurse über Algorithmen besucht, nur um zu erfahren, dass diese für die meisten Probleme der realen Welt nicht geeignet sind. Aber geben Sie noch nicht auf! Die Menschen sind kreativ und müssen diese Probleme sowieso lösen, so dass es in der Praxis oft Wege gibt, ein NP-komplettes Problem zu bewältigen. Wir zeigen zunächst, dass einige Spezialfälle von NP-kompletten Problemen tatsächlich in polynomieller Zeit gelöst werden können. Dann betrachten wir exakte Algorithmen, die eine Lösung viel schneller finden als der Brute-Force-Algorithmus. Wir schließen mit Approximationsalgorithmen, die in polynomieller Zeit arbeiten und eine Lösung finden, die nahe am Optimum liegt.