Titlebook: Kombinatorische Optimierung; Theorie und Algorith Bernhard Korte,Jens Vygen Textbook 20081st edition Springer-Verlag Berlin Heidelberg 2008

发酵

Ganzzahlige Optimierung,In diesem Kapitel betrachten wir lineare Programme mit ganzzahligen Nebenbedingungen.

cylinder

,Kürzeste Wege,Eines der bekanntesten kombinatorischen Optimierungsprobleme ist, einen kürzesten Weg zwischen zwei bestimmten Knoten eines Digraphen zu finden.

牲畜栏

Maximale Matchings,Die Matching-Theorie ist eines der klassischen und wichtigsten Gebiete der Kombinatorik und der kombinatorischen Optimierung. In diesem Kapitel sind sämtliche Graphen ungerichtet. Wir erinnern daran, dass ein Matching aus einer Menge von paarweise disjunkten Kanten besteht.

不能仁慈

Das Knapsack-Problem,Das . und das ., die beide in vorausgegangenen Kapiteln besprochen worden sind, gehören zu den ”schwersten“ Problemen, für die ein polynomieller Algorithmus bekannt ist. In diesem Kapitel werden wir uns mit dem folgenden Problem befassen, welches sich in einem gewissen Sinne als das ”leichteste“ .-schwere Problem herausstellen wird.

Eclampsia

Bin-Packing,Angenommen, wir haben . Objekte verschiedener fester Größen und einige Behälter von gleicher Größe. Unser Problem ist es, die Objekte den Behältern zuzuordnen, mit dem Ziel, die Anzahl der benutzten Behälter zu minimieren. Natürlich darf die Gesamtgröße der einem Behälter zugeordneten Objekte die Größe des Behälters nicht übersteigen.

一起平行

Transfusion

暗指

Lineare Optimierung,n jedoch nicht als eine umfassende Einführung in die lineare Optimierung betrachtet werden. Dem mit der linearen Optimierung nicht vertrauten Leser seien die am Ende des Kapitels angegebenen Texte empfohlen.

恶意

,Algorithmen für lineare Optimierung,aber Nachteile. Im Gegensatz zu den anderen beiden, gibt es bis dato keine Variante des ., die bewiesenermaßen polynomiell läuft. In den Abschnitten 4.4 und 4.5 präsentieren wir die . und beweisen, dass sie zu einem polynomiellen Algorithmus für die . führt. Die . ist jedoch zu ineffizient, um in de

effrontery

,Aufspannende Bäume und Arboreszenzen,Städte verbindet. Die zu mietenden Kabelverbindungen sollen alle Städte auf die billigste Weise miteinander verbinden. Dieses Problem stellt man natürlich durch einen Graphen dar: Die Knoten sind die Städte und die Kanten die Kabelverbindungen. Nach Satz 2.4 sind die minimalen zusammenhängenden aufs