Combinatorial optimization - Cheatsheet

Greedy-Algorithmen und ihre Anwendungen

Definition:

Ein Greedy-Algorithmus trifft in jedem Schritt eine lokal optimale Wahl in der Hoffnung, dass diese Wahl zu einer global optimalen Lösung führt.

Details:

• Einfachheit: leicht zu implementieren und laufen oft schnell.
• Verwendbarkeit: gut für Optimierungsprobleme mit dem Greedy-Kriterium.
• Gibt nicht immer die optimale Lösung: funktioniert nicht für alle Probleme, z.B. Rucksackproblem.
• Beispiele: Kruskal-Algorithmus (Minimum Spanning Tree), Dijkstra-Algorithmus (kürzeste Wege), Huffman-Codierung.
• Komplexität: oft polynomial in der Zeit, z. B. \(O(E \, \log V)\) für Dijkstra.

Dynamische Programmierung

Definition:

Dynamische Programmierung: Methode zur Lösung komplexer Optimierungsprobleme durch Zerlegung in Teilprobleme, deren Lösungen gespeichert werden, um Redundanz zu vermeiden.

Details:

• Grundprinzip: Teile-und-herrsche, Memoisierung
• Aufbau rekursiver Formeln, z.B. \[ C(i, j) = \text{min}(C(i-1, j), C(i, j-1)) + c(i, j) \]
• Nutzen bei Problemen mit optimaler Substruktur und überlappenden Teilproblemen
• Beispiel: Knapsack-Problem, Kürzeste-Wege-Problem

Branch-and-Bound Techniken

Definition:

Methode zur Lösung von Optimierungsproblemen durch systematische Erkundung von Lösungsräumen und sukzessives Beschneiden mittels Schranken.

Details:

• Startet mit der Lösung eines entspannten Problems, um Schranken zu bestimmen.
• Teilt das Probleminst auf in Teilprobleme (Branching).
• Berechnet Schranken für Teilprobleme und verwirft unbrauchbare (Bounding).
• Fortführung, bis optimale Lösung gefunden oder alle Möglichkeiten ausgeschlossen sind.
• Gebraucht in Integer Programming und Mixed-Integer Programming.
• Wichtig: Bounding kann durch Upper und Lower Bounds erfolgen.

Der Simplex-Algorithmus und seine Varianten

Definition:

Ein Algorithmus zur Lösung linearer Optimierungsprobleme durch schrittweises Durchlaufen von Ecken des zulässigen Bereichs.

Details:

• Wird verwendet für LP-Probleme (Lineare Programmierungsprobleme).
• Beginnt meist an einer Ecklösung und bewegt sich entlang der Kanten des Polyeders in Richtung der optimalen Lösung.
• Pivot-Operationen zur Auswahl der nächsten Basislösung.
• Kriterien: Wähle Variable mit höchstem reduzierten Kostenwert und ersetze die ausscheidende Basisvariable.
• Frontier-Pivot- und Dual-Simplex-Varianten optimieren bestimmte Aspekte des Algorithmus.
• Alternativen: Revised Simplex, Dual Simplex, Primal-Dual Methoden.
• Jeder Schritt des Algorithmus reduziert die Dimension des Suchraums.
• Kann degenerieren, Zyklusproblem vermeidbar mit Bland's Rule.

Maximale Flüsse in Graphen

Definition:

Berechnung des maximalen Flusses in einem Netzwerk-Graphen, bei dem der Fluss von einer Quelle zu einer Senke maximiert wird

Details:

• Verwende den Ford-Fulkerson Algorithmus zur Lösung
• Netzwerk besteht aus Quelle (s), Senke (t) und Knoten mit Kapazitäten
• Flusserhaltung: \(\sum_{v}f(u,v) = 0\) für jeden Knoten u ≠ Quelle, Senke
• Kantenkapazität: Fluss auf einer Kante (u,v) darf die Kapazität c(u,v) nicht überschreiten: \(f(u,v) \leq c(u,v)\)
• Max-Flow Min-Cut Theorem: Maximaler Fluss = minimale Schnittkapazität des Graphens

Analyse der Zeitkomplexität von Algorithmen

Definition:

Bewertung der Effizienz eines Algorithmus bezüglich der Laufzeit in Abhängigkeit von der Eingabegröße.

Details:

• Asymptotische Notationen: \(O\big(f(n)\big), \Omega\big(f(n)\big), \Theta\big(f(n)\big)\)
• Best/Worst/Average Case Analyse
• Polynomielle vs. exponentielle Zeitkomplexität
• Zeitkomplexität beeinflusst Skalierbarkeit und Praktikabilität eines Algorithmus

Reduktionen und Beweise der NP-Vollständigkeit

Definition:

Reduktion bietet Möglichkeit, ein Problem auf anderes zurückzuführen. Beweis der NP-Vollständigkeit zeigt, dass Problem zu schlimmsten in NP gehört.

Details:

• Ein Problem A ist NP-vollständig, wenn A in NP liegt und jedes Problem in NP polynomial auf A reduzierbar ist.
• Reduktion: Um Problem A auf Problem B zu reduzieren, transformiere jede Instanz von A in eine von B so, dass Lösung für B auch Lösung für A liefert.
• Beliebte Reduktionen: SAT zu 3-SAT, CLIQUE zu VERTEX-COVER.
• Beweise: Zeige, dass existierendes NP-vollständiges Problem auf das neue reduziert werden kann.
• Wichtig für Entscheidbarkeit und Ressourcenabschätzung in der kombinatorischen Optimierung.