6 Einführung in die Komplexitätstheorie In den vorherigen Kapiteln haben wir bereits einige theoretische Probleme kennenge- lernt. Wir haben insbesondere gesehen, dass sich einige Probleme schneller lösen (bzw. approximieren) lassen als andere. Außerdem scheint es Probleme zu geben, bei denen man schnell den Mut verliert, eine exakte Lösung in Polynomialzeit zu berechnen. Diese Probleme scheinen schwerer zu sein als andere. Was ist die Schwere eines Problems? Die Komplexitätstheorie befasst sich noch weitergehend mit der Frage nach der Komplexität von Problemen, dh. man versucht zu klassifizieren wie schwer Probleme sind. In diesem Kapitel werden wir die Komplexitätsklassen P und NP einführen und wol- len dann die Begriffe der NP-schwere und NP-vollständigkeit verstehen. Im Anschluss werden wir einige Beispiele NP-vollständiger Probleme studieren. 6.1 Einleitung: Cliquenproblem Als erstes Beispiel betrachten wir das sogenannte Cliquenproblem auf Graphen. Eine Clique ist eine Teilmenge C ⊆ V , wobei {u, v} ∈ E für alle u, v ∈ C mit u 6= v. Das Cliquenproblem können wir nun wie folgt angeben: Gegeben: Ein ungerichteter Graph G = (V, E) und eine Zahl k ≥ 1. Entscheide: Hat der Graph G eine Clique C ⊆ V mit mindestens k Knoten (d.h. mit |C| ≥ k)? Dies ist ein sogenanntes Entscheidungsproblem, welches also als Antwort Ja oder Nein gibt. Beispiel 6.1. Man betrachte den folgenden Graphen G = (V, E) mit V = {1, 2, 3, 4, 5} und E = {{1, 2}, {1, 3}, {2, 3}, {3, 4}, {3, 5}}: 2 b 1 b b 3 b b 4 5 Hier ist C = {1, 2, 3} eine Clique der Größe 3, aber C = {2, 3, 4} ist keine Clique. 200 6.1 Einleitung: Cliquenproblem Offensichtlich löst der folgende Algorithmus das Problem exakt: Algorithmus: Teste für alle V 0 ⊆ V mit |V 0 | = k, ob V 0 eine Clique bildet. Wir bezeichnen mit T (G, k) seine Laufzeit für eine Eingabe (G, k). Lemma 6.2. Der obige Algorithmus hat im schlimmsten Fall mindestens exponentielle Laufzeit; d.h. T (G, k) ≥ 2|V |/2 für k = |V |/2. Beweis. Für |V | = n, k = n/2 und n gerade: Der Test für jedes V 0 erfordert Ω(k 2 ) Schritte. Es gibt nk viele k-elementige Teilmengen. Dann erhalten wir hier mit   n n(n − 1) · (n/2 + 1) = ≥ 2n/2 n/2 n/2(n/2 − 1) · 1 mindestens eine exponentielle Laufzeit. Frage: Gibt es schnellere (bzw. insbesondere polynomielle) Algorithmen? Definition 6.3. (i) Ein Alphabet Σ ist eine endliche Menge an Symbolen. Σ∗ ist die Menge aller endlichen Wörter über Σ. (ii) Für jedes x ∈ Σ∗ bezeichne |x| die Länge von x. Bemerkung 6.4. Jeder Algorithmus arbeitet auf einem Alphabet (d.h. seine Eingaben und Ausgaben sind Elemente aus Σ∗ ). Für einen Algorithmus A, bezeichnet A(x) die Ausgabe zur Eingabe x ∈ Σ∗ . Die Laufzeit eines Algorithmus A zur Eingabe x (gegeben durch die Anzahl der aus- geführten Operationen) wird durch TA (x) bezeichnet. Die Worst Case Laufzeit zu Ein- gaben der Größe n ist TA (n) = max{TA (x)|x ∈ Σ∗ , |x| = n}. Definition 6.5. (i) Eine Teilmenge L ⊆ Σ∗ heißt Sprache. (ii) Ein Entscheidungsproblem ist ein Tripel (L, U, Σ) wobei L, U Sprachen sind und L ⊆ U. (iii) Ein Algorithmus A löst das Entscheidungsproblem (L, U, Σ) (oder auch A entschei- det die Sprache L bezüglich U ), wenn für alle x ∈ U gilt: – x ∈ L impliziert A(x) = 1, – x 6∈ L impliziert A(x) = 0. Häufig ist U = Σ∗ . Dann sagt man, dass A die Sprache L ⊆ Σ∗ entscheidet. Das Cliquenproblem etwa können wir als Sprache (Menge von Wörtern) wie folgt darstellen: CLIQU E = {u#v | u ∈ {0, 1}∗ stellt Adjazenzmatrix von G dar, v ∈ {0, 1}∗ stellt k dar, G hat Clique mit k Knoten }. 201 6 Einführung in die Komplexitätstheorie Hierbei ist Σ∗ = {0, 1}∗ die Menge aller endlichen Wörter (inklusive dem leeren Wort ) über dem Alphabet Σ = {0, 1}. Bemerkung 6.6. u ist ein Wort der Länge O(|V |2 ), v ist ein Wort der Länge O(log |V |). 6.2 Komplexitätsklassen P, NP Definition 6.7. Die Menge aller polynomiell entscheidbaren Sprachen bzw. Entschei- dungsproblemen wird mit P bezeichnet: P = {L ⊆ Σ∗ | es existiert ein Algorithmus A, der L in Laufzeit TA (n) = O(nd ) mit d = O(1) entscheidet}. Neben P gibt es unter anderem auch die Klasse NP . Diese wird häufig über nicht- deterministische Algorithmen eingeführt (bei denen es zu jeder Eingabe eine endliche Menge von Rechenwegen gibt). Definition 6.8. Ein nicht-deterministischer Algorithmus entscheidet eine Sprache L, • wenn es für jedes Wort w ∈ L mindestens einen Rechenweg gibt, der w akzeptiert, • wenn jeder akzeptierende Rechenweg in polynomieller Zeit läuft und • wenn für jedes Wort w 6∈ L jeder Rechenweg w ablehnt. Die Anzahl der Rechenwege kann dabei exponentiell von der Eingabe abhängen. Die Klasse NP ist nun genau die Menge aller Sprachen, die durch einen nicht-deterministischen Algorithmus in Polynomialzeit entschieden werden können. Wir bedienen uns hier aller- dings einer alternativen Definition der Klasse NP über polynomielle Verifizier. Die so definierte Klassen von Problemen sind aber gleich. Definition 6.9. Es sei L ⊆ Σ∗ . Ein (deterministischer) Algorithmus, der auf Σ∗ × Σ∗ arbeitet, heißt ein Verifizierer für L, wenn L = {x ∈ Σ∗ |∃c ∈ Σ∗ mit A(x, c) = 1}. Hierbei nennt man ein Wort c mit A(x, c) = 1 ein Zertifikat für x (bzw. für die Aussage x ∈ L). Definition 6.10. Ein Algorithmus A ist ein polynomieller Verifizierer für eine Sprache L, wenn eine Konstante d existiert, so dass es für jedes x ∈ L ein Zertifikat c gibt mit TA (x, c) = O(|x|d ). Definition 6.11. Die Klasse aller polynomiell verifizierbaren Sprachen wird mit NP bezeichnet; d.h. NP = {L ⊆ Σ∗ | es existiert ein polynomieller Verifizierer für L}. 202 6.2 Komplexitätsklassen P, NP Satz 6.12. Es gilt P ⊆ NP . Beweis. Zu einem Entscheidungsproblem L aus P gibt es einen Algorithmus A, der L entscheidet. Diesen Algorithmus kann man als Verifizierer auffassen, der die zweite Eingabe c einfach ignoriert. Damit ist L auch in NP . Nun können wir auf das Cliquenproblem zurückkommen und die folgende Aussage beweisen. Lemma 6.13. Das Entscheidungsproblem k-Clique ist in NP . Beweis. Durch Angabe eines polynomiellen Verifizieres für k-Clique. Der Algorithmus bekommt neben der Eingabe (einen Graph G = (V, E) und eine Zahl k) ein Zertifikat (u.z. eine Teilmenge C ⊆ V ). Der Algorithmus testet dann, ob C eine Clique der Größe ≥ k ist. Der Test geht wie folgt: (1) prüfe für alle zweielementigen Teilmengen {u, v} ⊆ C, ob {u, v} ∈ E liegt. (2) gebe Ausgabe Ja aus, wenn jeder Test in (1) positiv ausfiel und |C| ≥ k ist. Ansonsten Ausgabe Nein. Schritt (1) geht in Zeit O(|C|2 ) = O(|V |2 ) und die Kardinalitätsprüfung in (2) in O(|C|) = O(|V |) Zeit. Da die Eingabelänge Ω(|V | + |E|) ist, ist die Laufzeit des Algo- rithmus polynomiell. Nachdem wir nun gesehen haben, wie die Klassen P und NP definiert haben, können wir den Begriff der Schwere genauer beleuchten. Dafür ist es notwendig zu verstehen, wann ein Problem auf ein anderes Problem reduziert werden kann. Wir benötigen die folgende Definition. Definition 6.14. Es seien L1 ⊆ Σ∗1 , L2 ⊆ Σ∗2 zwei Sprachen. (i) Eine Funktion f : Σ∗1 → Σ∗2 mit der Eigenschaft w ∈ L1 ⇔ f (w) ∈ L2 ∀w ∈ Σ∗1 heißt Transformation von L1 auf L2 . (ii) Eine solche Transformation heißt polynomielle Transformation, wenn es ein Po- lynom p und einen Algorithmus A gibt, der für alle w ∈ Σ∗1 die Ausgabe f (w) der Länge ≤ p(|w|) in (polynomieller) Zeit TA (w) ≤ p(|w|) berechnet. Dann heißt L1 polynomiell reduzierbar auf L2 . Als Notation verwenden wir L1 ≤ L2 . Endlich können wir den Begriff der NP -Schwere bzw. NP -Vollständigkeit formal fassen: Definition 6.15. (i) Eine Sprache L0 heißt NP-schwer, g.d.w. ∀L ∈ NP : L ≤ L0 . (ii) Eine Sprache L0 heißt NP-vollständig, g.d.w. L0 ∈ NP und ∀L ∈ NP gilt: L ≤ L0 . 203 6 Einführung in die Komplexitätstheorie Eine fundamentale Eigenschaft der NP-vollständigkeit ist die folgende: Satz 6.16. Es sei L0 NP-vollständig. Dann gilt P = NP , g.d.w. L0 ∈ P . Beweis. ⇒: Es sei P = NP . Zeige dann, dass L0 ∈ P . L0 ist NP-vollständig. Dann gilt insbesondere L0 ∈ NP . Wegen P = NP gilt dann L0 ∈ P . ⇐: Es sei L0 ∈ P . Zeige hier, dass P = NP . Da L0 ∈ P ist, gibt es einen Algorithmus A0 , der L0 in Polynomzeit T0 entscheidet. Es sei nun L ∈ NP beliebig gewählt. Zeige: L ∈ P . Da L0 NP-vollständig ist und L ∈ NP , gilt L ≤ L0 . Sei also Af ein Algorithmus, der die polynomielle Transformation f von L auf L0 in Polynomzeit Tf berechnet mit u ∈ L ⇔ f (u) ∈ L0 . Wir konstruieren A aus A0 und Af durch Hintereinanderschalten; siehe folgendes Bild: Af A0 ja u f (u) nein Zeit Tf (|u|) Zeit T0 (|f (u)|) Dann akzeptiert A ein Wort u, g.d.w. A0 das Wort f (u) akzeptiert. Dies ist äquivalent zu f (u) ∈ L0 bzw. u ∈ L. D.h. Algorithmus A entscheidet L mit Gesamtlaufzeit ≤ Tf (|u|)+T0 (|f (u)|) ≤ T (|u|) für ein Polynom T . Hierbei verwende, dass |f (u)| ≤ poly(|u|) und dass die Komposition von Polynomen wieder ein Polynom ergibt. Konsequenz von Satz 6.16: Wenn ein NP-vollständiges Entscheidungsproblem in P liegt, dann sind alle NP Entscheidungsprobleme in P . Die gleiche Aussage gilt auch für ein NP-schweres Problem. Offenes Problem der Komplexitätstheorie: Gilt P = NP oder P 6= NP ? Dies ist eines der wichtigsten offenen Probleme der Informatik. Es wurde vom Clay Mathematics Institute in die Liste der Millennium-Probleme aufgenommen; mit einem Preisgeld von 1-Million Dollar: www.claymath.org. Bemerkung 6.17. Wenn L1 ≤ L2 und L2 ≤ L3 , dann gilt auch L1 ≤ L3 . Beweis. siehe Übung. Korollar 6.18. Ist L0 NP-vollständig, L0 ≤ L1 und L1 ∈ NP , so ist auch L1 NP - vollständig. 204 6.3 Definition von P und NP per Turingmaschine Beweis. Zeige die folgende Behauptung: ∀L ∈ NP gilt L ≤ L1 . Sei dazu L ∈ NP beliebig gewählt. Zeige dann die Aussage L ≤ L1 . Wegen der NP - vollständigkeit von L0 und da L ∈ NP ist, gilt L ≤ L0 . Nach Voraussetzung gilt zusätzlich L0 ≤ L1 . Da die Relation ≤ transitiv ist (siehe Bemerkung 6.17), gilt dann: L ≤ L1 . Da L1 ∈ NP wegen der Voraussetzung, ist daher L1 auch NP-vollständig. Das obige Ergebnis in Korollar 6.18 ermöglicht uns, NP-vollständige Probleme aus bekannten NP-vollständigen Problemen zu konstruieren (bzw. deren NP-vollständigkeit zu beweisen). Für diese Entscheidungsprobleme gibt es keine polynomiellen Algorithmen, außer P = NP . 6.3 Definition von P und NP per Turingmaschine Eine nicht-deterministische Turingmaschine (NDTM) hat die Form: M = (Q, Γ, q0 , δ, F ). Hierbei beschreibt Q die nicht-leere endliche Zustandsmenge, Γ das Arbeitsalphabet, wobei Γ ⊃ Σ gilt (dabei ist Σ das Eingabealphabet). Die Zustandsmenge enthält den Anfangszustand q0 ∈ Q und die Endzustandsmenge F ⊂ Q. Zuletzt beschreibt δ die Übergangsfunktion: δ : Q × Γ −→ 2Q×Γ×{−1,0,1} . Es gilt, dass |δ(q, a)| = 0, 1, 2, . . . sein kann, man also mehrere mögliche Folgezustände haben kann. Arbeitsfeld u a u q Ein Übergang δ(q, a) → (q 0 , a0 , −1/1/0) besagt: im Zustand q mit a auf dem Arbeits- feld (AF) drucke a0 auf AF, bewege den Schreiblesekopf (bzw. das AF) nach links, rechts oder bleibe stehen und gehe danach in Zustand q 0 über. Die möglichen Berechnungen einer NDTM wird über Konfigurationen (die die Band- inschrift plus den Zustand enthalten) beschrieben, wobei eine Konfiguration c wie folgt definiert ist: c ∈ Γ∗ × Q × Γ × Γ∗ u q a v, 205 6 Einführung in die Komplexitätstheorie wobei u und v Wörter sind, q ein Zustand und a der Buchstabe auf dem AF ist. Für u = u0 b, v sei die Folgekonfiguration von uqav definiert durch: u0 q 0 ba0 v falls δ(q, a) = (a0 , 1, q 0 ) u0 ba0 q 0 v falls δ(q, a) = (a0 , −1, q 0 ) u0 bq 0 a0 v falls δ(q, a) = (a0 , 0, q 0 ) Als Notation verwenden wir C ` C 0 ; dabei ist C 0 die Folgekonfiguration von C. Berechnung zu Wörtern bzw. Eingaben: Hierbei ist die Startkonfiguration durch q0 [w gegeben, wobei [ ein Sonderzeichen 'Blank' (bzw. ein Leerzeichen) darstellt mit [ ∈ Γ\Σ. Eine Konfiguration C nennt man Stopkonfiguration, falls keine Folgekonfiguration von C existiert. Eine Berechnung zu einer Eingabe w ∈ Σ∗ kann dann durch eine Folge C0 , . . . , Ck von Konfigurationen dargestellt werden, wobei C0 die Startkonfiguration zu einer Eingabe w ist, Ci ` Ci+1 , für alle i < k gilt und Ck eine Stopkonfiguration ist. Eine Berechnung heißt genau dann akzeptierend, wenn der Zustand von Ck in F liegt. Sei L ⊆ Σ∗ und T : N → N. M akzeptiert L [in nicht deterministischer Zeit T ] genau dann wenn ∀w ∈ Σ∗ : (w ∈ L ⇐⇒ ∃ akzeptierende Berechnung von M zu w [mit Länge ≤ T (|w|)]. Damit können wir die Zugehörigkeit zu der Komplexitätsklasse NP nun definieren. Definition 6.19. Eine Sprache L ⊂ Σ∗ ist in NP ⇐⇒ ∃ eine NDTM M über Alphabet Γ ⊃ Σ und ein Polynom T , so dass gilt: M akzeptiert L in nicht deterministischer Zeit T. Deterministische Turingmaschine (DTM) Falls |δ(q, a)| ≤ 1 ∀(q, a) ∈ Q × Γ, es also höchstens einen gültigen Übergang aus jedem Zustand gibt, nennt man eine Turingma- schine deterministisch. Die Berechnung der DTM ist analog zu NDTMs über Konfigu- rationen definiert. Eine DTM M entscheidet L [in deterministischer Zeit T ] genau dann wenn für alle Wörter w ∈ Σ∗ die Berechnung von w mit einer Stopkonfiguration endet [und Länge ≤ T (|w|) hat]. Dabei liegt der Zustand der Stopkonfigurationen in F , genau dann wenn w in L liegt. Die Zugehörigkeit zu der Komplexitätsklasse P wird nun analog definiert. Definition 6.20. L ⊂ Σ∗ ∈ P ⇐⇒ ∃ eine DTM M über Alphabet Γ ⊃ Σ und ein Poly- nom T , so dass M die Sprache L in Zeit T entscheidet. Nun bleibt zu zeigen, dass beide gezeigten Definitionen der Komplexitätsklasse NP äquivalent sind, sie also die gleiche Klasse beschreiben. Satz 6.21. Die Klassen der Sprachen bezüglich Verifizierer und NDTM sind äquivalent und beschreiben beide die gleiche Klasse NP . Beweis. ” ⊃ ” : Sei N eine NDTM, die eine Sprache L in Zeit nc für eine Konstante c entscheidet. Für jedes x ∈ L gibt es eine Folge nicht-deterministischer Übergänge, 206 6.4 Satisfiability Problem (SAT) so dass N bei Eingabe x einen akzeptierenden Zustand qacc erreicht. Diese Folge kann durch einen String u der Länge nc über einem Alphabet σ 0 mit O(1) vielen Buchstaben repräsentiert werden (hierbei hängt die Kardinalität von σ 0 von der maximalen Anzahl von Verzweigungen (d.h. |δ(q, a)|) ab. Dann folgt direkt, dass es eine DTM M gibt, die bei Eingabe < x, u > genau dieselben Berechnungen durchführt, also die gleichen Übergänge wie N macht. Für die Eingabe x ∈ L folgt also auch, dass M einen akzeptierenden Zustand erreichen muss. Dann ist M also auch ein Verifizierer für L. ” ⊂ ” : Sei L ⊆ Σ∗ gegeben und sei M ein Verifizierer für L. Sei p : N → N ein Polynom, das die Länge der Zertifikate angibt. Sei nc die Laufzeit der DTM M , wobei c wieder eine Konstante ist. Eine NDTM N , die w in Polynomzeit entscheidet, kann bei Eingabe x ∈ Σ∗ wie folgt vorgehen: Phase (1): Nutze nicht-deterministische Entscheidungen um einen beliebigen String u der Länge poly(|x|), also polynomiell in |x|, auf ein Arbeitsband zu schreiben. Phase (2): Simuliere M bei Eingabe < x, u >. Dann folgt direkt, dass N in Polynomzeit entscheidet, da M diese Eingabe in Polynomzeit verifizieren kann. 6.4 Satisfiability Problem (SAT) Der Kanadier Stephen A. Cook begründete 1971 die Klasse der NP-vollständigen Proble- me in NP , indem er zeigte, dass ein NP-vollständiges Problem existiert. Dieses Problem ist das sogenannte Satisfiability Problem (SAT). Leonid Levin hatte einen vergleichbaren Satz 1973 veröffentlicht. Satisfiability Problem (SAT) Das Satisfiability Problem (SAT) formalisiert die Frage nach der Erfüllbarkeit eines aussagenlogischen Ausdrucks. Aussagenlogische Ausdrücke sind zusammengesetzt aus Variablen und den elementaren Operatoren/Junktoren ∧ (und), ∨ (oder) und ¬ (nicht). Die Variablen sind Boolesche Variablen und wir notieren sie als xi, dh. x0, x1, x10, x11, . . . und so weiter. Für jede Variable xi existieren zwei Literale. Diese sind das positive Lite- ral xi und das negative Literal ¬xi. Aus den Literalen setzt man mit dem elementaren Operator ∨ (oder) sogenannte Klauseln zusammen, dh. disjunktive Ausdrücke der Form (y1 ∨ · · · ∨ yk ) mit Literalen y1 , . . . , yk . Ein Ausdruck α = C1 ∧ . . . ∧ Cm mit Klauseln C1 , . . . , Cm heißt Ausdruck in Kon- junktiver Normalform (KNF). Ein Ausdruck α heißt erfüllbar, g.d.w. eine Belegung φ der Variablen in α mit true, f alse existiert, so dass α unter der Belegung φ zu true ausgewertet wird (siehe Beispiel 6.23). Nun können wir das SAT-Problem als Sprache wie folgt angeben: SAT = {α | α Boolescher Ausdruck in KNF, α erfüllbar } Bemerkung 6.22. SAT ⊂ {x, 1, 0, ∨, ∧, ¬, (, )}∗ . Beispiel 6.23. Betrachte α = (x1∨x10)∧(x1∨¬x10)∧(x10). Wir erhalten die folgende Wahrheitstabelle: 207 6 Einführung in die Komplexitätstheorie x1 x10 α false false false true false false false true false true true true Die Belegung ψ(x1) = ψ(x10) = true ist eine erfüllende Belegung. Satz 6.24. (Cook, 1971/Levin, 1973): SAT ist NP-vollständig. Beweis. SAT ∈ NP Wir skizzieren dies für eine entsprechende nichtdeterministische Tu- ringmaschine mit den Zwischenergebnissen auf dem Turingband in Abb. 6.1. Salopp gesagt raten“ wir nichtdeterministisch eine Belegung der Variablen und prüfen ” dann, ob sie den Ausdruck erfüllt. α (1) ↓ det. α#Liste der auftretenden Variablen (2) ↓ nichtdet. α#Belegung der Variablen durch wahr/falsch: x101 → T 101 oder F 101. (3) ↓ det. α#Wert von α (4) ↓ det. F , wenn α = wahr; dummy-Zustand, falls α = falsch. Abb. 6.1: SAT ∈ NP: Alle vier Schritte sind in polynomieller Zeit ausführbar. L ∈ NP =⇒ L ≤ SAT Sei M eine NDTM und akzeptiere L in nichtdeterministischer Zeit T (für ein geeignetes Polynom T ). Wir suchen eine Transformation u → αu , die polynomzeitberechenbar ist mit u ∈ L ⇐⇒ αu ∈ SAT. Idee: αu wird so beschrieben, dass M für u in genau T (u) Schritten eine akzeptie- rende Stoppkonfiguration erreicht. Sei also M = (Q, Γ, q0 , δ, F ), wobei Q = {q0 , . . . , qs }, F = {qr , . . . , qs }, Γ = {a0 , . . . , am }, a0 = [. Ohne Ein- schränkung der Allgemeinheit gelte: Akzeptiert M das Wort u = aj1 . . . aj|u| mit einer Berechnung der Länge höchstens T (|u|), so akzeptiere M das Wort mit einer Berechung der Länge genau gleich T (|u|). Wir stellen δ durch eine Folge von Zeilen (Fünftupeln) z1 , . . . , z% der Form qaq 0 a0 β dar (für (q 0 , a0 , β) ∈ δ(q, a)). O.B.d.A betrachten wir nur Turingmaschinen, die nicht links vom Feld 0 arbeiten. Der zu konstruierende Ausdruck in KNF α enthält Variablen, deren Bedeutung in Tabelle 6.1 zusammengefasst ist. 208 6.4 Satisfiability Problem (SAT) Variablen in αk Bedeutung (wahr, falls. . . ) ztk nach t Schritten wird Zustand qk erreicht sti nach t Schritten ist Feld Nr. i das Arbeitsfeld btl nach t Schritten wird Zeile zl ausgeführt atij nach t Schritten steht auf Feld Nr. i der Buchstabe aj , Hierbei ist 0 ≤ t, i ≤ T (|u|), 0 ≤ k ≤ S, 1 ≤ l ≤ %, 0 ≤ j ≤ m. Tab. 6.1: Variablen in αk Die Anzahl der Variablen ist nach oben durch c · T (|u|)2 beschränkt, wobei c eine von der Turingmaschine abhängige Konstante ist. Wir bauen nun einen Ausdruck αu auf mit αu = αAnfang ∧ αEnde ∧ αEindeutig ∧ αÜbergang . Das Ziel ist, dass erfüllende Belegungen von αu den akzeptierenden Berechnungen in Zeit T (|u|) von M für u = aj1 . . . aj|u| entsprechen sollen. Wir setzen αAnfang = z00 ∧ s00 ∧ a000 ∧ a01j1 ∧ a02j2 ∧ · · · ∧ a0|u|j|u| ∧ a0(|u|+1)0 ∧ · · · ∧ a0 T (|u|) 0 αEnde = zT (|u|) r ∨ · · · ∨ zT (|u|) s genau ein Zustand“ ^ αEindeutig = ” 0≤t≤T (|u|) ∧ genau ein Arbeitsfeld“ ” ∧ für alle Felder i = 0, . . . , T (|u|) genau ein Buchstabe“  ” Den ersten Teil, genau ein Zustand“, schreiben wir als ” ^ (zt0 ∨ · · · ∨ zts ) ∧ ¬(zti ∧ ztj ), | {z } i6=j (¬zti ∨¬ztj ) die anderen Bedingungen analog. Wir setzen ^ αÜbergang = αt , 0≤t≤T (|u|) wobei αt Folgendes modelliert: • Buchstaben auf nicht-Arbeitsfeldern bleiben unverändert • Falls das Arbeitsfeld Nr. i hat und die l. Zeile qkl ajl qk̃l aj̃l βl ausgeführt wird, gilt: a) nach t Schritten wird qkl erreicht b) nach t Schritten steht auf Feld i der Buchstabe aj l c) nach t + 1 Schritten wird qk̃l erreicht 209 6 Einführung in die Komplexitätstheorie d) nach t + 1 Schritten steht auf Feld i Buchstabe aj̃l e) nach t + 1 Schritten hat das Arbeitsfeld die Nummer i + βl . Wir erhalten insgesamt: ^ ^  αt = ((¬sti ) ∧ atij ) → a(t+1)ij 0≤i≤T (|u|) 0≤j≤m ^  ∧ (sti ∧ btl ) → (ztkl ∧ atijl ∧ z(t+1)k̃l ∧ a(t+1)i̃l ∧ s(t+1)(i+βl ) ) 1 0 : ∃x0 ≥ 0 : ∀x ≥ xo : |f (x)| ≤ c · |g(x)| Man kann dies auch als fg(x) (x) → 0 für x → ∞. Nach dieser Definition gilt also auch dass δn = o(n), weswegen die beiden Schreibweisen austauschbar verwendet werden. Die Originale Formulierung der ETH verwendet die δn Notation, weswegen sie in unserer Formulierung der Theoreme verwendet wurde. 6.14 Hamiltonkreis Problem Das Hamitonkreis Problem (HK) is wie folgt definiert: Gegeben: Ein ungerichteter Graph G = (V, E) mit V = {v1 , . . . , vn }. Entscheide: Gibt es einen Hamiltonschen Kreis; d.h. eine Permutation π der Knoten (vπ(1) , . . . , vπ(n) ) mit {vπ(i) , vπ(i mod n+1) } ∈ E für alle i = 1, . . . , n? Beispiel 6.41. Der Graph in dem folgenden Bild hat einen entsprechenden Hamilton- kreis; dieser ist fettgezeichnet. 220 6.14 Hamiltonkreis Problem Satz 6.42. Das Hamiltonkreis Problem ist NP-vollständig. Bemerkung 6.43. Die gleiche Aussage gilt auch für gerichtete Graphen. Beweis. (a) HK is in NP: Wähle als Zertifikat eine Permutation π der Knoten und teste, ob {vpi(i) , vπ(i+1 mod n) } ∈ E ist für alle i = 1, . . . , n. (b) 3−SAT 0 ≤ HK: Gegeben seine SAT Formel mit genau 3 Literalen pro Klausel (ist ebenfalls NP-vollständig). Zur Beweisidee geben wir die folgende Graph-Konstruktionen an. Als erstes verwende die folgende A-Komponente: 1 3 5 6 7 8 2 4 Dann gibt es zwei Möglichkeiten, die Komponente A zu durchlaufen; siehe die folgen- den zwei Abbildungen: 1 3 2 4 1 3 2 4 Für jede Klausel verwenden wir die folgende Komponente B: 221 6 Einführung in die Komplexitätstheorie 1 2 3 4 Eine der vielen Möglichkeiten, wie B durchlaufen werden kann, ist im folgenden Bild dargestellt. 1 2 3 4 Insgesamt gibt es für jede nicht-leere Teilmenge der rechten Kanten {u1 , u2 }, {u2 , u3 }, {u3 , u4 } eine Möglichkeit die Komponente B zu durchlaufen. Bei einer leeren Teilmenge dieser Kanten funktioniert dies aber nicht; dies entsprecht dem Fall, dass alle Literale falsch gewählt worden sind. Als Kurzform für die Spezialkomponenten A und B verwenden wir: 1 3 5 2 4 222 6.14 Hamiltonkreis Problem 1 2 5 3 4 Im folgenden Beispiel zeigen wir die Konstruktion des Graphen G zu einem Booleschen Ausdruck F . Beispiel 6.44. Ausdruck F = (x1 ∨ ¬x2 ∨ x3 ) ∧ (¬x1 ∨ x2 ∨ ¬x3 ) ∧ (¬x1 ∨ ¬x2 ∨ x3 ) und der zugehörige konstruierte Graph G: 13 1 10 2 14 3 4 15 11 5 6 16 7 17 8 18 12 9 Für die Variablensetzung von Variable xi wählt man im rechten Pfad im obigen Bild jeweils zwischen zwei Knoten vi , wi für i = 1, . . . , n die rechte oder linke Kopie der Kante {vi , wi }. Die A-Komponenten werden nun genutzt um die Verbindung zwischen den Variablen und den Literalen in den B-Komponenten zu den entsprechenden Klauseln herzustellen. Dazu bezeichnen wir die u Knoten in der B-Komponente zu Klausel Fi mit ui1 , ui2 , ui3 und ui4 . Wenn das j.te Literal in Klausel Fi gleich xk ist, dann verbinden wir die Kante {uij , uij+1 } via einer A-Komponente mit der linken Kopie von {vk , wk }. Wenn das j.te Literal gleich ¬xk , so verbinden wir die Kante {uij , uij+1 } mit der rechten Kopie. Formal beweist man Ende die folgende Aussage: F is erfüllbar genau dann, wenn G einen Hamiltonkreis besitzt. Die Details findet man im Buch von Papadimitriou und Steiglitz. 223 6 Einführung in die Komplexitätstheorie Übungsaufgaben Übung 6.45. Die Eingabe des Problems SAT3 ist ein boolscher Ausdruck in KNF, für den entschieden werden soll, ob es mindestens 3 erfüllende Belegungen für diese Formel gibt. Zeigen Sie, dass SAT3 NP-vollständig ist. Übung 6.46. Eine NAE-k-SAT (Not-All-Equal) Formel hat folgende Form m i i V i=1 (z1 , . . . , zk ), wobei eine Klausel (z1i , . . . , zki ) mit Literalen z1i , . . . , zki genau dann erfüllt ist, wenn min- destens ein Literal zu wahr und mindestens ein Literal zu falsch ausgewertet wird. Beispiel: Für die NAE-3-SAT Formel (x, y, z) ∧ (¬x, y, z) ist durch x = y = z = true keine erfüllende Belegung gegeben, da in diesem Fall die erste Klausel nicht erfüllt ist. Bei der Belegung x = y = true und z = false hingegen ist die Formel erfüllt. Zeigen Sie in einem ersten Schritt, dass NAE-4-SAT NP-vollständig ist, und in einem zweiten Reduktionsschritt zeigen, dass ebenfalls NAE-3-SAT NP-vollständig ist. Übung 6.47. Ein Independent Set in einem Graphen G = (V, E) ist eine Menge von Knoten I, so dass für je zwei Knoten i, j ∈ I gilt, dass {i, j} 6∈ E. Für das Problem Independent Set ist ein Graph G = (V, E) sowie eine Zahl k ∈ N gegeben und es soll entschieden werden, ob es in G ein Independent Set mit k Knoten gibt. Zeigen Sie, dass das Problem Independent Set NP-vollständig ist. Übung 6.48. Ein Vertex Cover in einem Graphen G = (V, E) ist eine Menge von Knoten C ⊆ V so dass für jede Kante {v, w} ∈ E gilt das v ∈ C oder w ∈ C. Für das Problem Vertex Cover ist ein Graph G = (V, E) sowie eine Zahl k ∈ N gegeben und es soll entschieden werden, ob es in G ein Vertex Cover mit k Knoten gibt. Zeigen Sie, dass das Problem Vertex Cover NP-vollständig ist. Übung 6.49. In dem Problem Clique-Member ist ein Graph G = (V, E), ein Knoten v ∈ V sowie eine Zahl k ∈ N gegeben und es soll entschieden werden, ob es eine Clique mit k Knoten gibt, die den Knoten v enthält. Zeigen Sie, dass Clique-Member NP-vollständig ist. Übung 6.50. In dem Problem Clique-Nomember ist ein Graph G = (V, E), ein Knoten v ∈ V sowie eine Zahl k ∈ N gegeben und es soll entschieden werden, ob es eine Clique mit k Knoten gibt, die den Knoten v nicht enthält. Zeigen Sie, dass Clique-Nomember NP-vollständig ist, indem Sie eine Reduktion von Clique auf Clique-Nomember angeben. Übung 6.51. In dem Problem Z-Clique ist ein zusammenhängender Graph G = (V, E) und eine Zahl k ∈ N gegeben und es soll entschieden werden, ob G eine Clique mit k Knoten enthält. Zeigen Sie, dass Z-Clique NP-vollständig ist. Übung 6.52. Zeigen Sie, dass das Partition Problem ebenfalls NP-schwer ist, wenn eine Teilmenge A00 ⊆ A gesucht ist mit X X a=3 a. a∈A00 a∈A\A00 224 6.14 Hamiltonkreis Problem Übung 6.53. Für das Problem Subset Sum Cardinality seien n ganze Zahlen c1 , . . . , cn ∈ N>0 (wobei n gerade sei) sowie eine Zahl K ∈ N gegeben. Es P soll entschieden werden, ob es eine Teilmenge S ⊂ {1, . . . , n} gibt mit |S| = n/2 und i∈S ci = K. Zeigen Sie, dass das Problem Subset Sum Cardinality NP-vollständig ist. Übung 6.54. Eine Eingabe des Problems Even-Knapsack ist eine Menge von Items I, sowie ein Rucksack mit gerader Größe B (d.h es gibt b ∈ N mit B = 2b), sowie ein Profitwert P ∈ N. Jedes Item hat eine Größe si ∈ N und einen P Profit pi ∈ N. Das Entscheidungsproblem ist eine Teilmenge I 0 ⊆ I zu finden mit i∈I 0 si ≤ B und i∈I 0 pi ≥ P . P Zeigen Sie, dass Even-Knapsack NP-vollständig ist. Übung 6.55. Die Probleme Multiple-Choice-Knapsack (kurz MC-Knapsack) ist wie folgt definiert: Gegeben sind endliche Mengen C1 , . . . Ck ⊆ N × N von Items, eine Kapazität B ∈ N und ein Zielprofit P ∈ N. Wir bezeichnen Ci als Klasse von Items und für ein Item (w, p) ∈ Ci ist w das Gewicht und p der Profit des Items. Es soll entschieden werden, ob aus jeder Klasse Ci genau ein Item (wi , pi ) gewählt werden kann, sodass die gewählten Items gemeinsam P den Zielprofit erfüllen ohne die Kapazität zu überschreiten, d.h. i∈[k] pi ≥ P und i∈[k] wi ≤ B. P Das Problem ist in NP . Zeigen Sie: MC-Knapsack ist NP-vollständig 225 7 Approximative Algorithmen Das letzte Kapitel hat uns Einblicke in die Schwierigkeit der polynomiellen Berechen- barkeit gegeben. Wir wissen nun insbesondere, dass es viele Probleme gibt, deren exakte Lösung eine große, nicht-polynomielle Laufzeit benötigt - es sei denn, es gilt P = NP . In Ermangelung einer Eingebung zu der Frage, ob P = NP oder P 6= NP gilt, hat sich die Disziplin der Approximativen Algorithmen entwickelt; anstatt eine exakte Lösung zu verlangen, lässt man die Berechnung geringfügig schlechterer Lösungen zu, welche sich aber deutlich schneller berechnen lassen. Die exakte Lösung wird in diesem Sinne nur noch approximiert. In diesem Kapitel wollen wir einige solche Approximationsalgorithmen studieren. 7.1 Traveling Salesman Problem Gegeben: Eine Menge V = {1, . . . , n}, Distanzen d(i, j) ∈ Z+ ∪ {∞} für alle i, j ∈ {1, . . . , n} Gesucht: Eine minimale Rundreise, die jeden Knoten genau einmal besucht. Formal: Eine Lösung P ist gegeben durch eine Permutation Π von {1, . . . , n}, wobei die Länge der Tour ni=1 d(Π(i), Π(i + 1)) mit Π(n + 1) = Π(1) ist. Beispiel 7.1. Betrachte den folgenden Graphen mit 4 Knoten: 1 b 1 b 2 2 1 1 2 b b 4 1 3 Eine optimale Rundreise ist [1, 2, 3, 4, 1] mit Länge 4. Satz 7.2. Das Entscheidungsproblem zum Traveling Salesman Problem, ob eine Rund- reise mit Länge ≤ L existiert, ist NP-vollständig. Beweis. Dies folgt durch eine Reduktion vom Hamiltonkreis Problem: Wähle für jede Kante {u, v} ∈ E den Wert d(u, v) = 1 und für alle anderen Paare {u, v} 6∈ E den Wert d(u, v) = |V | + 1 sowie L = |V |. 226 7.1 Traveling Salesman Problem Durch Modifikation der Distanzen d(u, v) = ∞ für alle {u, v} 6∈ E, kann man sogar zeigen, dass es keinen approximativen Algorithmus für das allgemeine TSP Problem mit beschränkter Approximationsgüte gibt. Deswegen betrachten wir den symmetrischer Fall des TSP mit d(i, j) = d(j, i) und mit Erfüllung der Dreiecksungleichung (kurz: ∆-Ungleichung) d(i, j) ≤ d(i, k) + d(k, j); siehe auch folgendes Bild: k b i b b j Bemerkung 7.3. Das TSP bleibt NP-vollständig im symmetrischen Fall mit Dreiecks- ungleichung. Definition 7.4. Es sei G ein Multigraph mit parallelen Kanten. Ein Eulerscher Kreis ist ein Kreis, der jede Kante von G genau einmal besucht. Beispiel 7.5. (Königsberger Brückenproblem) A B C D Frage: Gibt es einen Rundweg, bei dem man über jede der 7 Brücken genau einmal läuft? Wir können das Brückenproblem in ein Graphproblem wie folgt transformieren: A B C D 227 7 Approximative Algorithmen Frage: Gibt es einen Eulerschen Kreis in dem Graphen? Die Frage nach einem Eulerschen Kreis lässt sich durch das folgende Kriterium beant- worten. Satz 7.6. Es sei G ein zusammenhängender Multigraph. Dann sind äquivalent: (a) G ist Eulersch (d.h. besitzt einen Eulerschen Kreis). (b) Jeder Knoten in G hat geraden Grad. (c) Die Kantenmenge von G kann in disjunkte Kreise zerlegt werden. Beweis. zur Übung. Mit Hilfe von dem obigen Kriterium sieht man nun, dass der obige Graph zum Königsberger Brückenproblem Knoten mit ungeradem Grad besitzt und es daher keinen entsprechenden Rundweg gibt. Wir betrachten nun den folgenden Algorithmus: Algorithmus ∆TSP1 (V = {1,...,n}, D = (d(i,j)) ) 1 Berechne einen minimalen spannenden Baum T des Graphen 2 Kn mit Distanzen d(i, j); 3 Konstruiere einen Multigraphen G aus T durch Verdoppeln 4 aller Kanten; 5 Bestimme einen Eulerschen Kreis K in G; 6 Bestimme eine Rundreise R aus K durch Abkürzungen; 7 return Rundreise R. Beispiel 7.7. Betrachte den Graphen mit V = {A, B, C, D, E}; siehe folgendes Bild (links). B b B b 1 2 1 C b 1 b A C b 1 b A 2 3 2 3 3 2 2 2 b b b b D 2 E D E Eine optimale Tour ist [C, B, D, E, A, C] der Länge 8. Der Algorithmus berechnet einen Baum T mit Gewicht w(T ) = 6; siehe obiges Bild (rechts). Wir erhalten den Graphen G durch Verdopplung der Kanten mit w(G) = 12; siehe folgendes Bild: 228 7.1 Traveling Salesman Problem B b B b 1 1 1 1 C b 1 b A C b 1 b A 1 1 2 2 2 3 2 2 2 2 2 2 b b b b D E D E Als Eulerschen Kreis erhalten wir K = [C, A, E, A, C, B, C, D, C] mit Länge d(K) = 12; und durch die Abkürzungen (d.h. Überspringen der schon vorher besuchten Knoten) erhalten wir die Rundreise R = [C, A, E, B, D, C] mit Länge d(R) = 10. Satz 7.8. Der Algorithmus ∆TSP1 hat eine multiplikative Güte 2; d.h. d(R) ≤ 2OP T (I), wobei OP T (I) die Länge einer minimalen Rundreise zu der Eingabe I mit V = {1, . . . , n} und Distanzen D = (d(i, j)) ist. Beweis. Die Behauptung folgt aus den folgenden Ungleichungen: (1) Das Gewicht w(T ) ≤ OP T (I), da eine optimale Rundreise nach Weglassen ei- ner Kante einen spannenden Baum ergibt und w(T ) das kleinste Gewicht eines spannenden Baums ist. (2) d(K) = 2w(T ) ≤ 2OP T (I). Die erste Gleichung folgt wegen der Verdopplung der Kanten und die Ungleichung wegen (1). (3) d(R) ≤ d(K). Das gilt, da wegen der ∆-Ungleichung die folgende Ungleichung gilt: d(i, j) ≤ d(i, `1 ) + d(`1 , `2 ) + . . . + d(`t , j); siehe auch folgendes Bild: `1 b `t b b b i j Formal zeigt man die obige Ungleichung per Induktion nach t ≥ 1. Bemerkung 7.9. Es gibt Beispiele für Eingaben I zu dem Traveling Salesman Problem mit OP T (I) = n, bei denen der Algorithmus ∆TSP1 eine Rundreise der Länge 2n − 2 berechnet. Beweis. Zur Beweisidee geben wir hier ein Beispiel mit n = 8 Knoten. Betrachte ei- nen Stern mit Knoten 8 in der Mitte und Knoten 1, . . . , 7 außen, die über einen Kreis miteinander verbunden sind. Formal haben wir V = {1, . . . , 8} und E = {{i, 8}|i = 1, . . . , 7} ∪ {{i, i + 1}|i = 1, . . . , 6} ∪ {{7, 1}}. Alle Kanten haben die Distanz 1; die anderen Nicht-Kanten haben Distanz 2. 229 7 Approximative Algorithmen Eine optimale TSP Tour hat die Form [1, 2, 3, 4, 5, 6, 7, 8, 1] der Länge 8. Dagegen kann der MST Algorithmus einen Stern mit 8 als Mittelpunkt und allen anderen Knoten außen generieren; d.h. T = (V, E 0 ) hat die Kantenmenge E 0 = {{i, 8}|i = 1, . . . , 7}. Durch Verdopplung der Kanten erhalten wir einen Multigraphen mit 2n − 2 Kanten. Eine mögliche Eulertour ist [8, 1, 8, 3, 8, 5, 8, 7, 8, 2, 8, 4, 8, 6, 8]. Der Algorithmus erzeugt dann über die Abkürzungen die folgende Tour: [8, 1, 3, 5, 7, 2, 4, 6, 8] mit Länge 14 = 2n − 2. Definition 7.10. Ein Matching in einem ungerichteten Graphen G = (V, E) ist ei- ne Teilmenge E 0 ⊆ E von Kanten, von denen keine zwei Kanten einen gemeinsa- men P Endpunkt gemeinsam haben. 0Bei Gewichten d(i, j) auf den Kanten sei d(E ) = 0 {i,j}∈E 0 d(i, j) das Gewicht von E . Ein Matching ist perfekt, falls jeder Knoten v ∈ V dabei überdeckt wird; d.h. 2|E 0 | = |V |. Beispiel 7.11. Ein bipartiter Graph G und ein perfektes Matching: b b b b b b Satz 7.12. (Lawler 1976): Ein perfektes Matching in einem Graphen G = (V, E) mit minimalem Gewicht kann in Zeit O(|V |3 ) berechnet werden. Beweis. siehe z.B. Vorlesung Discrete Optimization. Eine bessere Approximationsgüte erhalten wir, in dem wir die Knoten mit ungeraden Grad optimaler durch Kanten augmentieren. Hier hilft uns ein Matching mit minimalem Gewicht. Man beachte, dass die Anzahl der Knoten mit ungeradem Grad gerade ist; siehe auch Lemma 5.4. Algorithmus ∆TSP2 (V = {1,...,n}, D = (d(i,j)) ) 1 Berechne einen minimalen spannenden Baum T des 2 Graphen Kn mit Gewichten d(i, j); 3 Bestimme die Menge X der Knoten in T, 4 die ungeraden Grad haben; 5 Bilde den vollständigen Graphen H auf X 230 7.1 Traveling Salesman Problem 6 mit Gewichten d(i, j) für i, j ∈ X mit i 6= j. 7 Bestimme ein perfektes Matching K in H mit minimalem 8 Gewicht. 9 Bilde den Multigraphen G, der aus T durch 10 Hinzufügen aller Kanten aus K entsteht. 11 Bestimme einen Eulerschen Kreis C in G; 12 Bestimme eine Rundreise R aus C durch Abkürzungen; 13 return Rundreise R. Satz 7.13. (Christofides): Der Algorithmus ∆TSP2 hat eine multiplikative Güte 1.5; d.h. d(R) ≤ 1.5OP T (I). Beweis. Es gilt d(C) = w(T ) + d(K) ≤ OP T (I) + d(K). Man zeige nun, dass d(K) ≤ OP T (I)/2. Daraus folgt dann die Behauptung. Sei dazu (i1 , . . . , i2m ) mit |X| = 2m die Reihenfolge, in der die Knoten von X in einer optimalen Tour δ von I durchlaufen werden. Betrachte die Matchings: M1 = {{i1 , i2 }, {i3 , i4 }, . . . , {i2m−1 , i2m }} M2 = {{i2 , i3 }, {i4 , i5 }, . . . , {i2m , i1 }} Betrachte eine optimale Tour und die Knoten aus X: x b b y i1 b b i2 b b b b i6 b b i3 b b b b b i5 i4 b Wegen der ∆-Ungleichung gilt: OP T (I) ≥ d(i1 , i2 ) + d(i2 , i3 ) + . . . + d(i2m , i1 ) = d(M1 ) + d(M2 ). Daher gilt: OP T (I) ≥ d(M1 ) + d(M2 ) ≥ 2d(K), da K ein perfektes Matching bezüglich X mit minimalem Gewicht ist. Deswegen gilt: d(K) ≤ OP T (I)/2 und damit die Behauptung. Beispiel 7.14. Zu unserem Graphen im obigen Beispiel erhalten wir den folgenden induzierten Graphen H rechts mit einem perfektem Matching K und Gewicht w(K) = 3: 231 7 Approximative Algorithmen Bb 1 2 H B b 3 b E C b 1 b A 2 3 2 3 1 2 2 3 3 2 K MST b b C 2 D b b D 2 E Als Multigraphen G erhalten wir dann B b B b 1 1 2 1 1 C b 1 b A C b 1 b A 2 2 2 2 b 2 b b 2 b D E D E Ein Eulerkreis in G ist C = [C, B, C, A, E, D, C] und nach den Abkürzungen erhalten wir R = [C, B, A, E, D, C] mit Länge d(R) = 9. Lemma 7.15. Es gibt Beispiele für Eingaben I zu dem Traveling Salesman Problem mit OP T (I) = n, bei denen der Algorithmus ∆TSP2 von Christofides eine Rundreise der Länge (n − 1) + bn/2c berechnet. Beweis. zur Übung. 7.2 Rucksackproblem Dass das Rucksackproblem NP-vollständig ist, haben wir schon am Ende des letzten Ka- pitels gesehen. Hier wollen wir nun einige einfache Approximationsalgorithmen studieren. Gegeben: • n Gegenstände mit Gewichten w0 , . . . , wn−1 ∈ N und Gewinnen p0 , . . . , pn−1 ∈ N. • Rucksack der Kapazität B ∈ N. Gesucht: Teilmenge I ⊆ {0, . . . , n − 1} mit i∈I wi ≤ B und P X X X pi = max{ pi |I 0 ⊆ {0, . . . , n − 1}, wi ≤ B}. i∈I i∈I 0 i∈I 0 232 7.2 Rucksackproblem Satz 7.16. Das Entscheidungsproblem zum Rucksackproblem ist NP-vollständig; sogar wenn wi = pi für alle i = 0, . . . , n − 1. Beweis. siehe Kapitel Einführung in die Komplexitätstheorie. Zunächst betrachten wir einen einfachen Greedy Algorithmus (GA): Algorithmus GA(I = ((w0 , p0 ), . . . , (wn−1 , pn−1 ), B)) 1 sortiere die Gegenstände, so dass p0 /w0 ≥ p1 /w1 ≥ . . . ≥ pn−1 /wn−1 ; 2 setze S = ∅; 3 for i = P0 to n − 1 do 4 if ( j∈S wj ) + wi ≤ B then 5 S = S ∪ {i} 6 fi 7 od 8 return(S). Es sei GA(I) der Gesamtgewinn der durch Algorithmus GA berechneten Lösung S ⊆ {0, . . . , n − 1} und OP T (I) der Gesamtgewinn einer optimalen Lösung zur Eingabe I. Satz 7.17. (a) Die Laufzeit des Algorithmus GA ist O(n log n). (b) Der Algorithmus GA hat eine multiplikative Güte größer gleich B−1 (d.h. OP T (I)/GA(I) ≥ (B − 1)). Der Algorithmus GA hat daher keine konstante Worst-Case Güte. Beweis. Zu (a): hierzu speichere bei jedem Hinzufügen eines Gegenstands die momentan benutze Kapazität K. Dann geht Schritt (2 − 8) in O(n) Zeit. Die Gesamtlaufzeit ergibt sich durch das Sortieren in O(n log n). Zu (b): Betrachte das folgende Beispiel: I = ((w0 , p0 ) = (1, 1), (w1 , p1 ) = (B, B − 1), B). Hier gilt p0 /w0 = 1 und p1 /w1 = (B − 1)/B < 1. Der Algorithmus liefert hier S = {0} mit Gewinn 1; optimal ist aber Sopt = {1} mit Gewinn B − 1. In diesem Fall gilt OP T (I)/GA(I) = B − 1. D.h. im allgemeinen Fall ist die Rate unbeschränkt. Hinweis: Man beachte, dass GA in dem obigen Beispiel das Element mit maximalem Profit pmax ignoriert hat. Aus diesem Grunde betrachten wir eine leichte Modifikation von GA, die sofort hilft die Approximationsgüte zu beschränken. Algorithmus MGA(I = ((w0 , p0 ), . . . , (wn−1 , pn−1 ), B)) 1 berechne Lösung S1 mit Algorithmus GA, 2 berechne Lösung S2 = {j} mit pj = maxi∈{0,...,n−1} pi , 3 wähle Lösung S ∈ {S1 , S2 } mit größerem Gewinn. 4 return(S). 233 7 Approximative Algorithmen Es sei MGA(I) der Gesamtgewinn der durch Algorithmus MGA berechneten Lösung S ⊆ {0, . . . , n − 1} und OP T (I) der Gesamtgewinn einer optimalen Lösung zur Eingabe I. Satz 7.18. Die Worst-Case Güte von Algorithmus MGA ist 2 (d.h. OP T (I)/MGA(I) ≤ 2 für alle Eingaben I). Beweis. Betrachte relaxierte Version des Rucksackproblems, bei dem Gegenstände frak- tional genommen werden dürfen. Es sei OP Tf (I) der maximale Wert einer fraktionalen Lösung x∗ . Es gilt dann OP T (I) ≤ OP Tf (I), da der Lösungsraum sich vergrößert und ein Max-Problem vorliegt. Eine fraktionale Lösung x∗ von max nj=1 xj pj mit j xj wj ≤ B und xj ∈ [0, 1] für P P alle j = 1, . . . , n nimmt Gegenstände in der sortierten Reihenfolge p1 /w1 ≥ p2 /w2 ≥ . . . ≥ pn /wn , wobei die ersten k Gegenstände ganzzahlig (d.h. x∗j = 1) und der letzte Gegenstand fraktional mit x∗k+1 ∈ [0, 1) gewählt wird. Beachte: Es gilt kj=1 wj ≤ B und k+1 j=1 wj > B. Insgesamt haben wir P P Pk+1 ∗ j=1 xj wj = B. Falls wir einen fraktionalen Gegenstand haben mit x∗k+1 > 0 ist, so gilt kj=1 wj < B. P Im Folgenden zeigen wir, dass eine optimale fraktionalen Lösung die obige Form hat. Angenommen, wir haben ein Teilstück eines Gegenstands ` > k + 1 der Länge x∗` w` im Rucksack mit p` /w` < pk+1 /wk+1 und x∗` > 0. Dann muss ein anderes Stück (1 − x∗i )wi mit i ≤ k +1 und x∗i < 1 im Rucksack fehlen (wegen den obigen Bedingungen). Betrachte die minimale Länge length = min{(1 − x∗i )wi , x∗` w` }. Das folgende Bild veranschaulicht die genaue Situation: pj wj (1 − x∗i )wi x∗` w` Rucksack: grün y` w` ... ... ... ... 1 2 i k ` n wj austauschen Dann gilt length = yi wi = y` w` mit yi ∈ (0, 1 − x∗i ] und y` ∈ (0, x∗` ] und pi /wi ≥ pk+1 /wk+1 > p` /w` . Frage: Wie bestimmt man yi , y` ? Man beachte, dass length = min{(1 − x∗i )wi , x∗` w` } > 0. Fall 1: (1 − x∗i )wi = length. Hier setze yi = (1 − x∗i ) und y` = length/w` . Fall 2: x∗` w` = length. Hier setze y` = x∗` und yi = length/wi . 234 7.2 Rucksackproblem Ersetze nun die Länge y` w` in der Lösung durch yi wi . Der Profitgewinn durch diesen Austausch ist dann yi pi − y` p` und es gilt: yi pi − y` p` > yi (p` /w` )wi − y` p` = yi wi p` /w` − y` p` = y` w` p` /w` − y` p` = y` p` − y` p` = 0. D.h. der Profitgewinn ist echt positiv und damit kann ein solcher obiger Fall nicht auftreten. Nun kommen wir zur Abschätzung der Approximationsgüte: Da k + 1 das erste Item ist, dass der Algorithmus GA nicht nimmt, gilt OP Tf (I) ≤ GA(I) + pk+1 . Der Algorithmus MGA berechnet Lösung mit Wert GA(I) oder pmax ≥ pk+1 (bzw. sogar genauer mit Wert max{GA(I), pmax }). Daher gilt OP T (I) ≤ OP Tf (I) ≤ GA(I) + pk+1 ≤ GA(I) + pmax ≤ 2 max{GA(I), pmax } = 2 · MGA(I) Bemerkung 7.19. (a) Der Algorithmus MGA läuft in Zeit O(n log n). (b) Durch eine Modifikation von MGA können wir auch einen approximativen Algo- rithmus angeben mit Worst Case Güte 2, der in O(n) Zeit läuft. Beweis. Wir verwenden als Idee zur Laufzeitverbesserung (b) hierzu den Median-Algorithmus um das sogenannte Split-Item k + 1 in O(n) Zeit zu finden. Der folgende Algorithmus verallgemeinert die Idee vom MGA Algorithmus, in dem er alle k-elementigen Teilmengen durchprobiert, in den Rucksack vorplaziert, wenn das möglich ist, und mit Hilfe vom GA Algorithmus die Restkapazität auffüllt. Algorithmus von Sahni Gegeben: Parameter k ∈ {0, . . . , n}. Idee: Für jedes k definiere Algorithmus Ak wie folgt: (1) wähle eine Teilmenge S mit |S| ≤ k Gegenständen, die am Anfang im Rucksack liegen, (2) wende Algorithmus GA auf die übrigen Elemente an und füge die ausgewählten Gegenstände zusätzlich in den Rucksack ein. 235 7 Approximative Algorithmen Wende (1) + (2) auf alle möglichen Teilmengen S mit |S| ≤ k an und wähle Lösung mit maximalem Gewinn. Die Technik nennt man k-Enumeration. Es sei Ak (I) der Gewinn der Lösung, den der Algorithmus Ak von Sahni bezüglich einer Eingabe I und Parameter k ∈ {0, . . . , n} produziert. Satz 7.20. Für alle k ≥ 1 gilt: Ak hat Güte ≤ 1 + 1/k und Laufzeit TAk (n) = O(nk+1 ). Beweis. siehe Vorlesung Effiziente Algorithmus. Idee für ein schnelleres Verfahren: Konstruiere aus dem exakten Algorithmus Knapsack aus Kapitel 2 zum Rucksackproblem einen polynomiellen approximativen Algorithmus. Erinnerung: Das dynamische Programm zum Rucksackproblem hat eine nicht-polynomielle (bzw. eine sogenannte pseudo-polynomielle) Laufzeit O(n2 ·pmax ), wobei pmax = max{pi |0 ≤ i ≤ n − 1}. Hierbei könnte pmax exponentiell in der Eingabegröße sein; siehe auch Be- merkung 2.20. Idee zu Algorithmus AK (1) konstruiere eine Eingabe IK mit Gewinnen p0i = bpi /Kc (alle anderen Größen wi und B bleiben gleich). (2) wende Algorithmus Knapsack auf Eingabe IK an. Der Algorithmus AK berechnet eine Lösung S ⊆ {0, . . . , n−1} mit Größe P i∈S wi ≤ B und maximalem Gewinn i∈S p0i . P Wir entwickeln aus AK ein Verfahren A durch die Wahl pmax K= . (1/ + 1)n Satz 7.21. Der Algorithmus A läuft in Zeit O(n3 /) und hat eine Worst-Case Güte OP T (I)/A (I) ≤ 1 + . Man nennt eine solche Familie von Algorithmen (A ) ein vollständiges polynomielles Approximationsschema (FPTAS). Beweis. (a) zur Laufzeit: Für die skalierten Profite gilt: p0max = maxi p0i = maxi bpi /Kc = maxi bpi /pmax (1/ + 1)nc = b(1/ + 1)nc = O(n/). Der Algorithmus Knapsack angewandt auf die skalierte Instanz hat dann eine Laufzeit von O(n2 p0max ) = O(n2 n/) = O(n3 /). (b) zur Güte: Es gilt zunächst OP T (I) ≤ K · OP T (IK ) + K · n (1) Da p0i = bpi /Kc ≥ pi /K − 1, haben wir pi ≤ K · (p0i + 1) und deswegen haben wir 236 7.2 Rucksackproblem pi ≤ i∈Iopt (Kp0i + K) P P OP T (I) = i∈Iopt 0 P ≤ i∈Iopt Kpi + K · n ≤ K · OP T (IK ) + K · n Beachte, dass Iopt eine zulässige Lösung von IK ist und (IK )opt i.a. ein höheren Gewinn als Iopt bezüglich Instanz IK hat. Daneben gilt: K · OP T (IK ) ≤ AK (I) (2) Da p0i ≤ pi /K gilt K · OP T (IK ) = K · i∈(IK )opt p0i ≤ K · i∈(IK )opt pi /K P P P = i∈(IK )opt pi ≤ AK (I). Aus (1) + (2) folgt OP T (I) ≤ AK (I) + K · n. Da alle wi ≤ B (ansonsten kann Gegenstand i aus der Instanz gelöscht werden), gilt OP T (I) ≥ pmax = maxi pi . Wir erhalten OP T (I) AK (I) + Kn ≤ A (I) AK (I) Kn =1+ AK (I) Kn ≤1+ OP T (I) − Kn Kn ≤1+ pmax − Kn = 1 + . Die letzte Gleichung gilt, da pmax Kn (1/+1)n · n = pmax pmax − Kn pmax − (1/+1)n n 1 1 (1/+1) 1/+1 = 1 = 1/+1−1 1 − (1/+1) 1/+1 1 = = . 1/ Weitere Approximationsschema • O(n2 /) (Ibarra und Kim 1975). • O(n log(1/) + 1/4 ) (Lawler 1979). 237 7 Approximative Algorithmen • O(n min{log n, log(1/)} + 1/2 log(1/) min{n, 1/ log(1/)}) (Kellerer, Pferschy 2004). • Õ(n + (1/)5/2 ) (Rhee 2015). • Õ(n + (1/)12/5 ) (Chan 2018). • Õ(n + (1/)9/4 ) (Jin 2019). In der Õ Notation vernachlässigt man log(.)-Terme in der Laufzeit. Bemerkung 7.22. Es gibt kein FPTAS mit einer Laufzeit O((n + 1/)2−δ ), außer (min, +) Convolution hat einen Algorithmus mit einer subquadratischen Laufzeit (Cygan u.a. 2017 bzw. Künnemann u.a. 2017). 7.3 Scheduling Der Begriff Scheduling bescheibt die Problematik der Erstellung eines Ablaufplans bzw. Schedules, der Prozessen zeitlich begrenzt Ressourcen, wie etwa Maschinen bzw. Prozes- soren oder Speicher, zuteilt. Dabei untersucht man die Optimierung bzw. Approximation diverser Zielfunktionen. Eine klassische Variante wird formal als P ||Cmax angegeben und lässt sich wie folgt formulieren. Gegeben: n Jobs J = {J1 , . . . , Jn } mit Ausführungszeiten p1 , . . . , pn ∈ N und m identische Maschinen. Gesucht: Partition von J in m Teilmengen B1 , . . . , Bm mit minimaler maximaler Last X Cmax = max pj . 1≤i≤m Jj ∈Bi Den Wert Cmax nennt man auch den Makespan des Schedules. Das Problem wird be- zeichnet durch P ||Cmax bzw. P m||Cmax , wenn die Anzahl der Maschinen m konstant ist. Im Folgenden betrachten wir eine Instanz für das Schedulingproblem P ||Cmax : Tab. 7.1: Schedulinginstanz Jj J1 J2 J3 J4 J5 m=2 pj 1 2 1 3 1 Für diese Instanz mit zwei Maschinen können wir etwa die beiden folgenden Ablauf- pläne/Schedules als zulässig erkennen: • B1 = {J1 , J2 , J5 }, B2 = {J4 , J5 } mit Makespan 4. 238 7.3 Scheduling M1 J1 J2 J3 M2 J4 J5 Zeit 0 1 2 3 4 5 • B1 = {J1 , J3 , J4 }, B2 = {J2 , J5 } mit Makespan 5. M1 J1 J3 J4 M2 J2 J5 Zeit 0 1 2 3 4 5 Man erkennt leicht, dass der erste Ablaufplan ein optimaler Ablaufplan ist. Der op- timale Makespan ist also 4. Wie schwer ist nun dieses Problem? Der folgende Satz gibt uns Auskunft. Satz 7.23. Das Schedulingproblem auf identischen Maschinen P m||Cmax ist NP-vollständig sogar für m = 2 Maschinen. Beweis. Dies folgt durch eine Reduktion des Partitionsproblems. Man mache sich klar, dass daraus unmittelbar auch die NP-Vollständigkeit von P ||Cmax folgt. Wir wollen nun einen ersten Approximationsalgorithmus studieren, den wir List- Scheduling nennen. Algorithmus ListScheduling(L=(J1 , . . . , Jn ),m) 1 for i=1 to m do 2 Ei = 0; Bi = ∅; 3 od 4 for j=1 to n do 5 wähle Job Jj aus Liste L; 6 wähle Maschine Mi mit minimaler Last Ei ; 7 Bi = Bi ∪ {Jj }; 8 Ei = Ei + pj ; 9 od Es sei LS(I) die Länge eines List Schedules und OP T (I) die Länge eines optimalen Schedules zur Eingabe I. Satz 7.24. (a) Für alle Eingaben I = (L, m) gilt LS(I)/OP T (I) ≤ 2 − 1/m. (b) Es existiert eine Eingabe I ∗ mit LS(I ∗ ) = (2 − 1/m)OP T (I ∗ ). Der Algorithmus hat also eine multiplikative Güte bzw. absolute Worst Case Güte von 2 − 1/m. 239 7 Approximative Algorithmen Beweis. Zu (a): O.B.d.A. hat Maschine M1 nach der Zuordnung die höchste Last L = j∈B1 pj (ansonsten nummeriere die Maschinen um). Es sei Jk der letzte Job, der auf P Maschine M1 fertig wird. Dann haben alle Maschinen eine Last Li ≥ L − pk . Zu dem Zeitpunkt, wo Jk der Maschine M1 zugeordnet wurde, hatte M1 die kleinste Last L − pk . Wir illustieren dies in Abb. 7.1. M1 Jk M2 M3 .. . Mm Zeit 0 L − pk L Abb. 7.1: Maschine M1 hat mit Jk bzw. ohne Jk die größte Last bzw. kleinste Last Daraus folgt sofort die folgende Abschätzung: n X pi ≥ m(L − pk ) + pk . i=1 Daneben gilt (da die gesamte Last Ppi auf m Maschinen verteilt werden muss und P mindestens eine Maschine eine Last ≥ pi /m hat): n X pi /m ≤ OP T (I). i=1 Da nun LS(I) = L ist, gilt n X OP T (I) ≥ pi /m ≥ m(L − pk )/m + pk /m i=1 = L − (1 − 1/m)pk = LS(I) − (1 − 1/m)pk Da OP T (I) ≥ pk folgt nun OP T (I) ≥ LS(I) − (1 − 1/m)OP T (I) bzw. LS(I) ≤ (2 − 1/m)OP T (I). Zu (b): zur Übung. Wir haben gesehen, dass ein erstaunlich einfacher Algorithmus schon eine Güte von 2 garantieren kann. Allerdings fällt auf, dass die beliebige Wahl des nächsten Jobs (in Zeile 5) mitunter schlecht sein kann. Es scheint besser zu sein, die Jobs absteigend ihrer Aus- führungszeit nach zu plazieren, was uns zum folgenden Algorithmus LPT Scheduling führt. 240 7.3 Scheduling Algorithmus LPT Scheduling(I=(J,,m)) 1 sortiere die Jobs in J so, dass p1 ≥ p2 . . . ≥ pn ; 2 wende den List Scheduling Algorithmus an auf I=(L,m) mit L=(J1 , . . . , Jn ) Es sei LP T (I) die Länge eines LPT Schedules bezüglich einer Eingabe I = (J, m). Satz 7.25. Der LPT Algorithmus hat eine absolute Worst Case Rate von 4/3 − 1/(3m); d.h. LP T (I) ≤ (4/3 − 1/(3m))OP T (I). (∗) Beweis. Annahme: Es existiert eine Jobmenge J und Maschinenzahl m, die die Be- hauptung (∗) nicht erfüllt. Der Satz gilt sofort für m = 1 (in diesem Fall gilt nämlich LP T (I) = OP T (I)). Daher nehmen wir an: m ≥ 2 und n ist minimal (d.h. wir haben ein minimales Gegenbeispiel). Annahme: Es existiert ein Job Jr mit r < n, für den die Fertigstellungszeit fr = LP T (I = (J, m)) gilt. Betrachte J 0 = {J1 , . . . , Jr } mit Liste L0 = (J1 , . . . , Jr ). Dann gilt LP T (I = (J, m)) = LP T (I 0 = (J 0 , m)) und der optimale Wert OP T (I 0 ) ≤ OP T (I). Damit haben wir LP T (I 0 ) LP T (I) ≥ > 4/3 − 1/(3m) OP T (I 0 ) OP T (I) ein kleineres Gegenbeispiel gefunden. Widerspruch zur Minimalität von n. Es gilt also fk < LP T (I = (J, m)) für alle k < n. Desweiteren haben wir die Unglei- chungen: n 1 X OP T (I) ≥ pi (1) m i=1 n−1 (2) X pi ≥ msn = m(LP T (I) − pn ), i=1 wobei sn der Startzeitpunkt von Job Jn ist. pn Jn m Jobs J1 , . . . , Jn−1 Zeit 0 sn LPT(J) Beachte: Alle Maschinen sind bis zum Zeitpunkt sn voll beschäftigt (d.h. keine Ma- 241 7 Approximative Algorithmen schine ist idle vor dem Zeitpunkt sn ). LP T (I) sn + pn = OP T (I) OP T (I) n−1 pn 1 X ≤(2) + pi OP T (I) mOP T (I) i=1 n (m − 1)pn 1 X = + pi mOP T (I) mOP T (I) i=1 (m − 1)pn ≤(1) + 1. mOP T (I) Da (∗) für I nicht gilt, folgt (m − 1)pn LP T (I) 1+ ≥ > 4/3 − 1/(3m). mOP T (I) OP T (I) Daraus folgt (m − 1)pn m−1 > 1/3 − 1/(3m) = mOP T (I) 3m bzw. OP T (I) pn > . 3 (d.h. der kleinste Job Jn ist größer als OP T (I)/3). Daraus folgt, dass keine Maschine in einem optimalen Schedule mehr als 2 Jobs ausführen kann. Als nächstes transformieren wir einen optimalen Schedule Dopt für solch eine Jobmenge mit pn > OP T (I)/3 in einen Schedule D̄opt , der zusätzliche Eigenschaften erfüllt. Transformation I.1 für Dopt . Gegeben sei ein Schedule Dopt mit Makespan Cmax und zwei Jobs Ji und Ji0 auf einer Maschine und zwei Jobs Jj und Jj 0 auf einer anderen Maschine, wobei pi > pj und pi0 > pj 0 ist. Ji Ji0 Jj Jj 0 Zeit 0 Wenn wir Ji0 und Jj 0 vertauschen, so erhalten wir den folgenden Schedule Dopt 0 mit Makespan Cmax ≤ Cmax : 0 242 7.3 Scheduling Ji Jj 0 Jj Ji0 Zeit 0 Transformation I.2 für Dopt . Gegeben sei ein Schedule Dopt mit Makespan Cmax und zwei Jobs Ji und Ji0 auf einer Maschine und ein Job Jj auf einer anderen Maschine, wobei pi > pj ist. Wenn wir den Job Ji0 auf die andere Maschine verschieben, so erhalten wir einen Schedule Dopt 0 ebenso mit Makespan Cmax 0 ≤ Cmax : Ji Ji0 verschieben Jj Zeit 0 Transformation II für Dopt . Gegeben sei ein Schedule Dopt mit Makespan Cmax und zwei Jobs Ji und Ji0 auf einer Maschine mit pi < pj . In diesem Fall vertauschen wir die Reihenfolge beider Jobs auf der entsprechenden Maschine: austauschen Ji Jj Zeit 0 Beachte: Keine der Transformationstypen I.1, I.2 oder II erhöht den Makespan. 243 7 Approximative Algorithmen Definition 7.26 (Lastfunktion). Bei gegebenen Lastwerten Li auf den Maschinen Mi in einem Schedule D ist die Lastfunktion L(D) = 1≤i pj , so folgt pj 0 ≥ pi0 , pi ≤ pk , pi ≥ pi0 , (∗∗) pj ≤ pk , pj ≥ pj 0 . Durch Umordnen der Maschinen in D∗ erhalten wir einen Schedule D̄opt : 244 7.3 Scheduling Jk1 Jk2 Jks Ji1 Ji01 Ji2 Ji02 Jit Ji0t Zeit 0 Hierbei gelten die Ungleichungen pk1 ≥ . . . ≥ pks sowie pi1 ≥ . . . ≥ pit und wegen (∗∗) haben wir p0i1 ≤ . . . ≤ p0it und pks ≥ pi1 sowie pit ≥ p0it . Damit haben wir die folgende Ordnung der Jobs: pk1 ≥ . . . ≥ pks ≥ pi1 ≥ . . . ≥ pit ≥ p0it ≥ . . . p0i1 . Der Schedule D̄opt ist nun äquivalent zu einem List Schedule DL bei gegebener Lis- te L = (J1 , . . . , Jn ) mit p1 ≥ . . . ≥ pn (bis auf Vertauschen von Jobs mit gleicher Ausführungszeit). Daraus folgt aber LP T (I = (J, m)) = OP T (I = (J, m)). Wegen LP T (I)/OP T (I) > 4/3 − 1/(3m) erhalten wir nun aber einen Widerspruch (d.h. es kann kein Gegenbeispiel für die Ungleichung (∗) existieren). Bemerkung 7.28. Für jede Anzahl m von Maschinen existiert eine Eingabe Im ∗ = (J ∗ , m) mit ∗) LP T (Im 4 1 ∗) = − . OP T (Im 3 3m Beweis. zur Übung. Satz 7.29. Für jede Genauigkeit  > 0 gibt es einen approximativen Algorithmus A für P ||Cmax mit A (I) ≤ (1 + )OP T (I) und Laufzeit 2O(1/ log (1/)) + O(n). 2 Bemerkung 7.30. Eine Familie (A ) von solchen Algorithmen nennt man ein (effizi- entes) polynomielles Approximationsschema (EPTAS). Details: siehe Vorlesung Effiziente Algorithmen. 245 7 Approximative Algorithmen Übungsaufgaben Übung 7.31. Zeigen Sie: • Ein zusammenhängender ungerichteter Graph G = (V, E) enthält eine Eulertour genau dann, wenn jeder Knoten in V geraden Knotengrad hat. • Ein stark zusammenhängender gerichteter Graph G = (V, E) enthält eine Eulertour genau dann, wenn für jeden Knoten v ∈ V gilt, dass din (v) = dout (v). 246