next up previous contents
Nächste Seite: Knapsack Aufwärts: Effiziente Algorithmen und Datenstrukturen Vorherige Seite: FFT   Inhalt

Approximationsalgorithmen

Frage: Wie löst man ein NP-vollständiges Problem effizient?

Definition:
Ein Approximationsalgorithmus $ A$ berechnet zu jeder Probleminstanz $ I$ eine Lösung $ A(I)$, die möglichst nah an der optimalen Lösung $ OPT(I)$ der Instanz liegt.

Bemerkung:
Approximationsalgorithmen mit einem konstanten absoluten Fehler sind selten.

Definition:
Die Güte $ \rho$ eines Approximationsalgorithmus gibt an, wie nahe $ A(I)$ an der optimalen Lösung liegt:
$ \frac{1}{\rho} \leq \frac{A(I)}{OPT(I)} \leq \rho$ für alle I

Klassen von Approximationsalgorithmen:
1. $ PO$: in polynomialer Zeit optimal lösbar ($ P$)
2. $ FPTAS$: es existiert ein vollständig polynomiales Approximationsschema (beliebig gut)
3. $ PTAS$: es existiert ein polynomiales Approximationsschema (exp. Laufzeit in der Güte)
4. $ APX$: es exisitiert ein Approximationsalgorithmus mit Güte $ \rho \geq 1$ (zumindest irgendwie)
5. $ NPO$: jeder Approximationsalgorithmus ist beliebig schlecht
Die Klassen bilden für $ P \neq NP$ eine echte Hierarchie, für $ P=NP$ kollabieren sie.



Unterabschnitte

2003-10-08