Approximationsalgorithmen - Cheatsheet

Definition und Bedeutung von Approximationsalgorithmen

Definition:

Näherungsverfahren für Optimierungsprobleme, bei denen exakte Lösungen schwer oder unmöglich zu finden sind.

Details:

• Wichtige Klasse von Algorithmen in der Informatik
• Ziel: Annäherung an die optimale Lösung in akzeptabler Zeit
• Approximitätsverhältnis: \( k \)-Approximation liefert Lösung mit Kosten maximal \( k \)-fach der optimalen Kosten
• Typische Anwendung: NP-schwere Probleme
• Leistungsanalyse durch Worst-Case-Betrachtung
• Beispiele: Traveling Salesman Problem (TSP), Rucksackproblem
• Greedy-Algorithmen, lokale Suche und dynamische Programmierung als Techniken

Unterschiede zwischen exakten und Approximationsalgorithmen

Definition:

Vergleich zwischen Algorithmen, die genaue Lösungen liefern, und solchen, die Näherungslösungen liefern.

Details:

• Exakte Algorithmen: Berechnen präzise Lösungen für ein Problem.
• Approximationsalgorithmen: Liefern Lösungen, die nahe an der optimalen Lösung liegen, oft schneller berechenbar.
• Zeitkomplexität: Exakte Algorithmen oft NP-schwer, Approximationsalgorithmen effizienter.
• Gütemaß von Approximationsalgorithmen: Approximationsfaktor \(\rho \), wobei \(\rho = \frac{Z_{alg}}{Z_{opt}}\) für Minimierungsprobleme und \(\rho = \frac{Z_{opt}}{Z_{alg}}\) für Maximierungsprobleme.

Polynomial Time Approximation Scheme (PTAS) und Fully Polynomial Time Approximation Scheme (FPTAS)

Definition:

PTAS ist ein Algorithmus, der für jedes \( \frac{1}{\text{Rückstand}} \) eine Lösung findet, die höchstens \((1 + \frac{1}{\text{Rückstand}})\)-mal schlechter als die optimale Lösung ist. FPTAS ist ein spezieller Fall von PTAS, der in polynomialer Zeit sowohl in der Eingabelänge als auch in \( \frac{1}{\text{Rückstand}} \) läuft.

Details:

• PTAS: Für jedes \( \frac{1}{\text{Rückstand}} \) eine Lösung in polynomialer Zeit.
• FPTAS: Löst Problem in polynomialer Zeit bzgl. Eingabelänge und \( \frac{1}{\text{Rückstand}} \).
• PTAS: Laufzeit \(O(n^{f(\frac{1}{\text{Rückstand}})})\).
• FPTAS: Laufzeit \(O(\text{poly}(n, \frac{1}{\text{Rückstand}}))\).
• Beispiele: Rucksackproblem (FPTAS), temporäre Planung (PTAS).

Simplex-Algorithmus und Dualitätstheorie in der linearen Programmierung

Definition:

Simplex-Algorithmus: Algorithmus zur Lösung linearer Programme durch iterative Verbesserung. Dualitätstheorie: Behandelt Zusammenhänge zwischen Primal- und Dualproblemen in der linearen Programmierung.

Details:

• Simplex-Algorithmus startet an einer Ecke der zulässigen Lösungsmenge und bewegt sich entlang der Kanten zum Optimum.
• Dualitätstheorie: Jedes lineare Programm hat ein zugehöriges Dualproblem, dessen Lösung Informationen über das Primalproblem gibt.
• Schwache Dualität: Der optimale Zielfunktionswert des Dualproblems ist eine obere Schranke für das Primalproblem (im Maximierungsfall).
• Starke Dualität: Falls eine optimale Lösung existiert, stimmen die Zielfunktionswerte des Primal- und Dualproblems überein.
• Dualitätslücke: Differenz zwischen den Zielfunktionswerten von Primal- und Dualproblem (idealerweise null).
• Komplementäre Schlupfbedingungen: Beschreiben die Beziehung zwischen Primal- und Dualvariablen im optimalen Fall.

Randomisierte Algorithmen und ihre Anwendungen

Definition:

Randomisierte Algorithmen nutzen Zufallselemente zur Problemlösung und bieten oft einfachere Implementationen und geringere Laufzeiten als deterministische Algorithmen.

Details:

• Definition: Verwenden Zufall zur Entscheidungsfindung während der Problemlösung.
• Kategorien: Las-Vegas-Algorithmen (immer korrekt, zufällige Laufzeit), Monte-Carlo-Algorithmen (zufällige Genauigkeit, fixierte Laufzeit).
• Typische Anwendung: Optimierungsprobleme, NP-schwere Probleme, Approximationen.
• Beispiel: Randomisierte Schnell-Sort und Primzahltests.
• Wichtige Kenngrößen: Erwartete Laufzeit, Fehlerwahrscheinlichkeit.
• Hilfsmittel: Wahrscheinlichkeitsanalyse, Markov-Ungleichung, Chernoff-Schranken.

Approximationstechniken für MAX-SAT

Definition:

Approximationstechniken für MAX-SAT: Methoden, um Näherungslösungen für das MAX-SAT-Problem zu finden.

Details:

• MAX-SAT: Maximierungsvariante des SAT-Problems
• Ziel: Größtmögliche Anzahl erfüllbarer Klauseln in einer booleschen Formel finden
• Greedy-Algorithmen: Einfache Heuristiken basierend auf der Auswahl der nächsten besten Option
• Randomisierte Algorithmen: Nutzen Zufallsentscheidungen zur Lösungsfindung; liefern erwartete Güte
• Lineare Programmierung: Löst relaxierte Version des Problems; Rundung der Lösung zur Erzeugung einer ganzzahligen Lösung
• Performancegarantien: Maß für die Nähe der approximierten Lösung zur optimalen Lösung

Nähe- und Approximationsalgorithmen für das Traveling Salesman Problem (TSP)

Definition:

Nähe- und Approximationsalgorithmen bieten Lösungen für das TSP, die nahe an der optimalen Lösung liegen.

Details:

• Das TSP ist ein NP-schweres Problem.
• Hauptziel: Minimierung der Gesamtlänge der Tour, die alle Städte einmal besucht und zur Ausgangsstadt zurückkehrt.
• Bekannte Algorithmen: Nearest Neighbor, Minimum Spanning Tree (MST), Christofides.
• Approximation ratio: Verhältnis der gefundenen Lösung zur optimalen Lösung, z.B. Christofides: 1.5-Approximation.
• Greedy-Algorithmen nutzen lokale Optimierungen, liefern oft schnell gute, aber nicht optimale Ergebnisse.

Praktische Anwendungen von Approximationsalgorithmen für NP-schwere Probleme

Definition:

Ansatz zur Lösung von NP-schweren Problemen durch Algorithmen, die gute (aber nicht optimale) Lösungen in polynomialer Zeit liefern.

Details:

• Verwendet in Bereichen wie Logistik, Netzwerkdesign, und Scheduling.
• Beispiele: Traveling Salesman Problem (TSP), Knapsack-Problem, Vertex-Cover.
• Leistungsfähigkeit misst man durch Approximationsfaktor \(\alpha\): \[ \text{Kosten der Lösung durch den Algorithmus} \leq \alpha \times \text{Kosten der optimalen Lösung} \]
• Typische Strategien: Greedy-Algorithmen, Lineare Programmierung, dynamische Programmierung.