Approximationsalgorithmen

Approximationsalgorithmen lösen NP-harte Optimierungsprobleme in polynomialer Zeit und garantieren dabei eine Lösung, die nachweislich innerhalb eines festen Faktors des Optimums liegt, wodurch strenge Kompromisse zwischen Lösungsqualität und Handhabbarkeit ermöglicht werden.

Definition

Ein Approximationsalgorithmus für ein Optimierungsproblem ist ein polynomialzeitlicher Algorithmus, der eine zulässige Lösung liefert, deren Zielfunktionswert nachweislich innerhalb eines bewiesenen multiplikativen Faktors – des Approximationsverhältnisses – des optimalen Wertes liegt.

Scope

Dieses Thema behandelt polynomialzeitliche Algorithmen, die nahezu optimale Lösungen für schwierige Optimierungsprobleme liefern, das Approximationsverhältnis, das deren Qualität misst, und die wichtigsten Entwurfstechniken: Greedy- und lokale Suchheuristiken mit nachweisbaren Schranken, Lineare-Programmierung-Relaxation und -Rundung sowie die Primal-Dual-Methode. Es umfasst auch Approximationsschemata (PTAS und FPTAS) und die Existenz von Inapproximierbarkeitsergebnissen, die die Güte der Approximierbarkeit einiger Probleme begrenzen.

Core questions

• Wie wird die Qualität einer approximierten Lösung durch ein Approximationsverhältnis gemessen?
• Wie wandeln LP-Relaxation und -Rundung ein fraktionales Optimum in eine beschränkte ganzzahlige Lösung um?
• Wie liefern Greedy- und lokale Suchmethoden nachweisbare Approximationsgarantien?
• Was sind polynomialzeitliche Approximationsschemata, und welche Probleme lassen sie zu?
• Warum können einige Probleme beliebig gut approximiert werden, während andere überhaupt nicht approximiert werden können?

Key concepts

• Approximationsverhältnis
• NP-harte Optimierung
• Greedy-Approximation
• lokale Suche
• LP-Relaxation und -Rundung
• Primal-Dual-Methode
• PTAS und FPTAS
• Inapproximierbarkeit

Key theories

Approximationsverhältnis

Das Approximationsverhältnis begrenzt, wie weit die Lösung eines Algorithmus im schlimmsten Fall vom Optimum entfernt sein kann; eine c-Approximation garantiert eine Lösung innerhalb eines Faktors c des Optimums und bietet ein strenges Qualitätszertifikat für einen effizienten Algorithmus.

LP-Relaxation und -Rundung

Viele Approximationsalgorithmen relaxieren ein ganzzahliges Programm zu einem linearen Programm, lösen es effizient und runden die fraktionale Lösung zu einer ganzzahligen, während der Verlust begrenzt wird, was über Primal-Dual- oder Rundungsrahmen nachweisbare Verhältnisse liefert.

Clinical relevance

Approximationsalgorithmen machen unlösbare Optimierungsprobleme in der Praxis nutzbar: Methoden mit begrenztem Verhältnis für Set Cover, Vertex Cover, Facility Location, Scheduling und das Traveling Salesman Problem leiten reale Systeme in Logistik, Netzwerkdesign und Operations Research und liefern Lösungen mit Qualitätsgarantien anstelle von unbestätigten Heuristiken.

History

Das Feld begann in den 1970er Jahren mit Johnsons Analyse von Approximationsverhältnissen für Probleme wie Set Cover und Bin Packing sowie Christofides' Algorithmus von 1976 für das metrische Traveling Salesman Problem. Lineare-Programmierung- und Primal-Dual-Techniken reiften in den 1980er und 1990er Jahren, und probabilistisch überprüfbare Beweise (probabilistically checkable proofs) etablierten später starke Inapproximierbarkeitsergebnisse, die alle in Lehrbüchern von Vazirani sowie Williamson und Shmoys konsolidiert wurden.

Key figures

• Vijay Vazirani
• David Williamson
• David Shmoys
• David Johnson
• László Lovász

Seminal works

• vazirani2001
• williamson2011
• cormen2009

Frequently asked questions

Was garantiert ein 2-Approximationsalgorithmus?

Für ein Minimierungsproblem liefert eine 2-Approximation immer eine Lösung, deren Kosten höchstens doppelt so hoch sind wie die optimalen Kosten (und mindestens optimal für ein Maximierungsproblem, innerhalb eines Faktors von einem halben). Die Garantie gilt für jede Eingabe, egal wie adversarisch.

Kann jedes NP-harte Problem gut approximiert werden?

Nein. Einige Probleme lassen Approximationsschemata zu, die beliebig nahe am Optimum liegen, andere haben ein bestmögliches konstantes Verhältnis, und einige können nicht innerhalb eines vernünftigen Faktors approximiert werden, es sei denn, P ist gleich NP. Inapproximierbarkeitsergebnisse legen diese Grenzen formal fest.