Uni Trierfernau/Nalg0607/version1.pdf · INHALTSVERZEICHNIS 2 Inhaltsverzeichnis 1 Einfuhrung 7¨ 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Das

Naherungsalgorithmen

Vorlesungsskript

entstanden ab 2001, zunachst in Tubingen

Henning FernauLS Theoretische Informatik

Universitat Trieremail: [email protected]

LATEX-nisch in Teilen betreut vonThomas Bitschnau

1

INHALTSVERZEICHNIS 2

Inhaltsverzeichnis

1 Einfuhrung 7

1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 Das Knotenuberdeckungsproblem — ein einfuhrendes Beispiel 8

2 Uberdeckungsprobleme 14

2.1 Ein allgemeines Uberdeckungsproblem . . . . . . . . . . . . . 14

2.2 Gewichtetes Knotenuberdeckungsproblem . . . . . . . . . . . 15

2.3 Gewichtsreduktion . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4 2-Approximationen fur das gewichtete Knotenuberdeckungs-problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.5 Randomisierte r-Approximation . . . . . . . . . . . . . . . . . 22

2.6 (∆-)Hitting-Set — eine weitere Anwendung der Satze uberlokale Verhaltinisse . . . . . . . . . . . . . . . . . . . . . . . . 23

3 Grundlegende Definitionen 29

3.1 Spezifikation von Optimierungsproblemen . . . . . . . . . . . 29

3.2 Problemvarianten . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.3 Die Klassen PO und NPO . . . . . . . . . . . . . . . . . . . . 30

3.4 MAXCLIQUE als Beispielproblem . . . . . . . . . . . . . . . 31

4 Greedy-Verfahren 35

4.1 Das Rucksackproblem . . . . . . . . . . . . . . . . . . . . . . 35

4.2 Unabhangige Mengen in Graphen . . . . . . . . . . . . . . . . 38

4.3 Das Handelsreisendenproblem . . . . . . . . . . . . . . . . . . 42

5 Partitionsprobleme 47

5.1 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.2 Bin Packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.3 Graphenfarben . . . . . . . . . . . . . . . . . . . . . . . . . . 54


6 Lokale Suche 56

6.1 Großtmoglicher (Kanten-)Schnitt (Maximum Cut MC) . . . . 56

7 Lineares Programmieren 58

7.1 Allgemeines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

7.2 Aquivalente Formulierungen . . . . . . . . . . . . . . . . . . . 58

7.3 Duale Programme . . . . . . . . . . . . . . . . . . . . . . . . 59

7.4 Ganzahliges Programmieren und Relaxation . . . . . . . . . . 60

7.5 Primal-Duale Algorithmen fur ILP . . . . . . . . . . . . . . . 61

8 Dynamisches Programmieren 64

8.1 Ein exakter Algorithmus fur das Rucksackproblem . . . . . . 64

8.2 Ein Naherungsverfahren fur das Rucksackproblem . . . . . . 66

9 Weitere Strategien 68

10 Absolute Approximation 71

11 Relative Approximation; die Klasse APX 74

11.1 Definitionen der Grundbegriffe . . . . . . . . . . . . . . . . . 74

11.2 MAXSAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

11.3 Das Handelsreisendenproblem MTS . . . . . . . . . . . . . . . 76

11.4 Grenzen der Approximierbarkeit — Die Gap-Technik . . . . . 81

11.5 Anwendung auf das Graphenfarbeproblem . . . . . . . . . . . 82

12 Polynomzeit-Approximationsschemata 85

12.1 Kleinstmogliche Zweiteilung (Minimum Partition, MP) . . . . 85

12.2 Das Kreisscheibenuberdeckungsproblem (Disc Cover) . . . . . 88

12.3 Zum Zusammenhang mit der Konstruktion von Baker . . . . 91

12.4 APX versus PTAS . . . . . . . . . . . . . . . . . . . . . . . . 91

12.5 NP-Harte und Pseudo-Polynomialitat . . . . . . . . . . . . . 93


13 Zwischen APX und NPO 95

13.1 Das Mengenuberdeckungsproblem (Set Cover, SC) . . . . . . 95

13.2 Graphenfarben . . . . . . . . . . . . . . . . . . . . . . . . . . 99

14 Zwischen PTAS und APX 101

14.1 Kantenfarben . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

14.2 Bin Packing (BP) . . . . . . . . . . . . . . . . . . . . . . . . . 103

14.3 EIN PTAS∞ fur BP . . . . . . . . . . . . . . . . . . . . . . . 106

15 Approximationsklassen und Reduktionen 107

15.1 Erinnerung: Reduktion fur P versus NP . . . . . . . . . . . . 107

15.2 Die Welt von NPO-Problemen . . . . . . . . . . . . . . . . . 108

15.3 AP-Reduzierbarkeit . . . . . . . . . . . . . . . . . . . . . . . 110

15.4 NPO-Vollstandigkeit . . . . . . . . . . . . . . . . . . . . . . . 112

15.5 EXP-APX-Vollstandigkeit . . . . . . . . . . . . . . . . . . . . 115

15.6 APX-Vollstandigkeit . . . . . . . . . . . . . . . . . . . . . . . 115

15.7 Facetten der Harte fur Approximationen . . . . . . . . . . . . 118


Kurze Einfuhrung

Dies ist das Skriptum zu einer im Wintersemester 2001/2002 zunachst an derUniversitat Tubingen gehaltenen Vorlesung, die dann wiederholt gehaltenwurde, schließlich auch an der Universitat Trier. Der Kurs stutzt sich —sofern nicht anderes im laufenden Text angegeben wird— auf das Buch

G. Ausiello and P. Creczenzi and G. Gambosi and V. Kann andA. Marchetti-Spaccamela and M. Protasi: Complexity andApproximation; Combinatorial Optimization Problems andTheir Approximability Properties, Springer, 1999.

Aufgrund des enzyklopadischen Umfangs dieses Werkes kann in einer zwei-stundigen Vorlesung naturlich nur ein Bruchteil der Thematik abgehandeltwerden. Als erganzende Lektture ist das Buch aber jederzeit empfohlen.

Die Vorlesung gliedert sich in drei große Teile:

• In dem die drei ersten Kapitel umfassenden Einfuhrungsteil wird Grund-satzliches zur P–NP-Problematik und diesbezuglichen Losungsansatzengesagt und am Knotenuberdeckungsproblem durchgesprochen. Ein sol-cher Losungsansatz sind Approximationsalgorithmen.

• Die Kapitel 4 bis 9 behandeln verschiedene Techniken zum Entwurfvon Naherungsalgorithmen.

• Die Kapitel 10 bis 15 betrachten Optimierungsprobleme mehr phano-menologisch: Welche Typen von Naherungsalgorithmen gibt es, undwie “gute” Approximationen sind zu erwarten (sofern man einige kom-plexitatstheoretische Annahmen trifft)?


Eine Einfuhrung in die Thematik

Der Einfuhrungsteil gliedert sich in drei Abschnitte:

• Im Einfuhrungsteil (im engeren Sinne) werden wir Querbezuge zu an-deren, verwandten Themen herstellen und diese dann anhand von ein-fachen Algorithmen fur das Knotenuberdeckungsproblem erlautern.

• Das Knotenuberdeckungsproblem soll uns veranlassen, uns zum Ein-stieg Uberdeckungsprobleme allgemein genauer anzusehen. Dabei wer-den wir den Satz uber lokale Verhaltnisse als einen ersten recht allge-meinen Ansatz zum Nachweis der Qualitat von Naherungsalgorithmenkennen lernen.

• Im dritten Abschnitt werden wir den eigentlichen Gegenstand der Vor-lesung, namlich Optimierungsprobleme, formal naher untersuchen. Da-bei werden wir auch Reduktionen zwischen verschiedenen Problemva-rianten besprechen.

1 EINFUHRUNG 7

1 Einfuhrung

1.1 Motivation

Viele interessante Probleme (aus der Praxis!) sind NP-hart; Es sind wohl keine Polynomzeitalgorithmen sind zu erwarten.

Mogliche Auswege:

• Heuristische Verfahren

– Ziel: schnelle Laufzeit

– ”hoffentlich“ wird ”gute“ Losung gefunden.↪→ keine ”mathematische“ Garantie, nur ”Empirie“.

– typische Beispiele: Greedy-Verfahren

• Randomisierte Verfahren

– finden optimale Losung ”mit großer Wahrscheinlichkeit“.Hinweis: Spezialvorlesung ”Randomisierte Algorithmen“ (wirdmanchmal angeboten)

• Parameterisierte Verfahren

– finden stets optimale Losung.

– versuchen, den nicht-polymiellen Laufzeitanteil auf einen (als kleinangenommenen) sogenannten Parameter zu beschranken.Hinweis: Spezialvorlesung ”Parameterisierte Algorithmen“

• Naherungsverfahren

– sind ”Heuristiken mit Leistungsgarantie“.

– Gute von Naherungsverfahren kann

∗ absolut oder∗ relativ zum Optimum gemessen werden

Da bis auf wenige Ausnahmen (z.B. Knotenfarbung in planaren Graphen we-gen des 4-Farbensatzes) das Auffinden von Losungen, die absoluten Fehler-schranken genugen, meist ebenfalls NP-hart ist, hier zumeist: Beschrankungauf relative Naherungen.

1 EINFUHRUNG 8

1.2 Das Knotenuberdeckungsproblem — ein einfuhrendesBeispiel

Eine Knotenuberdeckung (engl: vertex cover) eines Graphen G = (V,E)ist eine Menge C ⊆ V derart, dass fur jede Kante e = {v1, v2} ∈ E gilt:e ∩ C 6= ∅, d.h., e wird durch einen Knoten aus C abgedeckt.Das Problem, eine kleinstmogliche Knotenuberdeckung zu finden, ist einesder ”Kernprobleme“ im Buch von Garey/Johnson, d.h. insbesondere, es istNP-vollstandig.

Wo findet sich das Knotenuberdeckungsproblem in der Praxis?

a) Im Mittelalter: Errichtung von Raubritterburgen an wichtigen Handels-wegenBesonderheit: planarer Graph⇒1.5-Approximation und besser !

b) In der Neuzeit: Eine internationale Firma will in Duty-Free-Shops aufinternationalen Flughafen so vertreten sein, dass jeder Passagier, derauf einer ”Hauptroute“ fliegt, beim Start- oder beim Zielflughafen dieGelegenheit hat, bei einer Filiale der Firma einzukaufen.Hier: i.a. nichtplanarer Graph!

c) ”Fehlergraphen“

Beispiel: Wie groß ist ein kleinstmogliches VC ?

Einfache Beobachtungen und Regeln

• Zwei Knoten in einem Dreieck gehoren in ein VC.

1 EINFUHRUNG 9

• Wenn Wahlmoglichkeit besteht, nimm solche Knoten, die “noch mehr”abdecken konnen.; Nimm Nachbarn eines Grad-1-Knotens ins VC.; Gibt es in einem Dreieck einen Knoten vom Grad zwei, so nimmdessen beide Nachbarn ins VC.

Unser Beispiel: Wir wenden die Regeln an und finden 6 VC-Knoten.

Die Regeln kaskadieren ; 5 weitere VC-Knoten.

Was bleibt ubrig ?

1 EINFUHRUNG 10

Eine einfache Greedy-Strategie

als Beispiel fur ein heuristisches Verfahren ohne GutegarantieAufruf: GreedyVC(G, ∅)GreedyVC (G, C)

• Falls G leer, gib C aus. exit.

• Suche Knoten v mit maximalem Grad in G.

• Berechne GreedyVC (G− v, C∪{v})Hinweis: G − v entsteht aus G, indem v mit anliegenden Kanten ausG geloscht wird.

Idee hierbei: ein Knoten hohen Grades ”deckt viel ab“.Leider gibt es keine Gutegarantie!

Wie arbeitet diese Strategie bei unserem Beispiel ? Die farbig hervorgeho-benen Knoten wurden (beispielsweise) durch die Greedy-Vorgehensweiseausgewahlt. Knoten gleichen Grades tragen dabei die gleiche Farbe.

1 EINFUHRUNG 11

Eine einfache Suchbaumstrategie

als Beispiel fur ein parametrisiertes VerfahrenAufruf: SuchbaumVC(G, ∅, k)Hinweis: k ist der Parameter, der die Uberdeckungsmengengroße beschrankt.

SuchbaumVC(G, C, k)

• Falls G leer, gib C aus; exit.

• Falls K = 0: exit.

• Nimm irgendeine Kante e ={v1, v2} aus G und verzweige:

1. Berechne SuchbaumVC(G− v1, C∪{v1}, k − 1)

2. Berechne SuchbaumVC(G− v2, C∪{v2}, k − 1)

Die Laufzeit hangt nur exponentiell vom Parameter ab.⇒ parameterisierter Algorithmus.

Man kann (und sollte) Suchbaume mit einfachen Regel kombinieren, welchein Polynomzeit einfache Falle losen konnen. Zwei solche Regeln hatten wirfur das Knotenuberdeckungsproblem entwickelt. Fur unser Beispiel bedeutetdies:

• Der ursprunglich ziemlich große Graph wird durch die Reduktionsre-geln stark verkleinert.

• Nach einmaligem Verzweigen wird der ubrigbleibende Graph vollstandigdurch die Reduktionsregeln erledigt.

1 EINFUHRUNG 12

Genauer zeigen die folgenden Bilder zunachst (farbkodiert) die beiden Ver-zweigungsfalle (rot und blau) und sodann, welche Knoten die Regeln noch je-weils hinzugenommen hatten, um schließlich zu einer gultigen Knotenuberdeckungzu gelangen.

Knotenorientierter Suchbaum, kombiniert mit den Regeln ; zwei Zweige

Der blaue Fall

Der rote Fall

Ergebnis fur unser Beispiel:

Die kleinste Knotenuberdeckung enthalt 16 Knoten.Eine kleinste Knotenuberdeckung wurde von der Heuristik gefunden.Die Verwendung von Reduktionsregeln hilft, die Verzweigungszahl bei Such-baumalgorithmen zu verringern.

Ein einfacher Naherungsalgorithmus

Aufruf: NeinfachVC(G, ∅)

NeinfachVC(G = (V,E), C)

• Falls E leer, gib C aus. exit.

• Nimm irgendeine Kante e = {v1, v2} aus Gund berechne NeinfachVC(G− {v1, v2}, C ∪ {v1, v2})

1 EINFUHRUNG 13

Dies ist ein 2-Approximations-Verfahren.Warum? Fur jede von NeinfachVC ausgewahlte Kante gilt: einer der beidenEckpunkte muss in einer optimalen Losung vorkommen, NeinfachVC istaber hochstens um Faktor 2 schlechter.

In unserem Beispiel konnten wir die rot gekennzeichneten Kanten auswahlen.Dies wurde uns zunachst alle roten und magentafarbenen Knoten in dieUberdeckung bringen. Naturlich ist es moglich (fur die Guteschranke al-lerdings unwesentlich), daraus eine inklusionsminimale, ebenfalls zulassigeLosung (also Knotenuberdeckung) auszurechnen, indem solange wie moglichemit einer Greedy-Strategie wiederum Knoten aus der bislang konstruiertenLosung entfernt werden. Dies konnte dazu fuhren, dass die mangentafarbe-nen Knoten nicht zu so einer Losung gehoren.

2 UBERDECKUNGSPROBLEME 14

2 Uberdeckungsprobleme

Nach: R.Bar-Yehuda: ”One for the price of two: a unified approach for ap-proximating covering problems“, Algorithmica 27, 131–144, 2000

Motivation

• Der einfache 2-Approximationsalgorithmus klappt so nicht im wichti-gen Fall von Graphen mit Knotengewichten.

• Klappt das intuitive Greedy-Verfahren ”leicht modifiziert“?

2.1 Ein allgemeines Uberdeckungsproblem

g ist gegeben durch ein Tripel (X, f, w), wobei

• X eine endliche Menge ist

• f : 2X → {0, 1} eine monotone Abbildung ist, d.h.A ⊆ B → f(A) ≤ f(B), und es gelte f(X) = 1,

• w : X → R+ ist die Gewichtsfunktion

Fur eine Menge Y ⊆ X definieren wir w(Y ) =∑

x∈y w(x) als Gewichtvon Y .

Bemerkung 2.1 Damit ist auch w monoton. Außerdem sind Gewichts-funktionen linear in dem Sinne, dass (w1 + w2)(C) = w1(C) + w2(C) gilt.

C ⊆ X ist Uberdeckung gdw. f(C) = 1. Ziel ist es, eine kleinstmoglicheUberdeckung (minimum cover) C∗ ⊆ X zu finden, die also

w(C∗) = min{w(C) | C ⊆ X, f(C) = 1}

erfullt. Eine Uberdeckung heißt r-Approximation, falls w(C) ≤ r ·w(C∗).


2.2 Gewichtetes Knotenuberdeckungsproblem

Ggb: gewichteter Graph, i.Z.: G = (V,E), w : V → R+

In obiger Terminologie:

X = V, f : V ′ →{

0, V ′ ist keine Knotenuberdeckung1, V ′ ist eine Knotenuberdeckung

f ist hier durch E gegeben und muss nicht explizit gespeichert werden bzw.gehort nicht zur Eingabe. Ein kleines Beispiel:

3

24

1

6 1 3

7

4

Ein kleines Beispiel: mit moglicher LosungDabei wurden rote Knoten in die Uberdeckung mit Hilfe der Große-Grad-Heuristik aufgenommen, wahrend sich die blauen Knoten aus der folgendenHeuristik ergaben: Ist Knoten vom Grad Eins, so nimm Nachbarn ! Bitteuberprufen Sie die Gute der Heuristiken in dem gegebenen Beispiel und inselbst gewahlten.

3

24

1

6 1 3

7

4

= 17+9 8

2.3 Gewichtsreduktion

Zerlegungsbeobachtung: Sind w1, w2 Gewichtsfunktionen, so gilt fur dieGewichte OPT (wi) der jeweiligen kleinstmoglichen Uberdeckungen:

OPT (w1) + OPT (w2) ≤ OPT (w1 + w2).


Beweis: Ist C∗ optimal fur w1 + w2 , so gilt:

OPT (w1 + w2) = (w1 + w2)(C∗)= w1(C∗) + w2(C∗)≥ OPT (w1) + OPT (w2)

Betrachte nun Gewichtsreduktionsfunktion δ : X → R+

mit ∀x ∈ X : 0 ≤ δ(x) ≤ w(x), d.h. δ und w − δ sind Gewichtsfunktionen.Wir definieren: ∆OPT := OPT (w)−OPT (w − δ).Zerlegungsbeobachtung ;

∆OPT = OPT (w)−OPT (w − δ)≥ OPT (δ) + OPT (w − δ)−OPT (w − δ)

Eine Gewichtsreduktion fuhrt daher zu einer Optimumsreduktion um we-nigstens OPT (δ).

Wir nennen δ r-effektiv, falls δ(X) ≤ r ·OPT (δ).

Betrachte folgenden Grundalgorithmus:

A(X, f, w) :

• Wahle r-effektive Gewichtsreduktion δ .

• Berechne durch B(X, f, w − δ) eine Uberdeckung C .

• Gib C an.

Der erwahnte Algorithmus B wird haufig A selbst wieder sein (oder eineleichte Modifikation).

Satz 2.2 Satz uber lokale VerhaltnisseLiefert B eine Uberdeckung C mit (w− δ)(C) ≤ r ·OPT (w− δ), 1 dann istw(C) ≤ r ·OPT (w), d.h. A ist r-Approximation.

Beweis:

w(C) = (w − δ)(C) + δ(C) [Linearitat]≤ (w − δ)(C) + δ(X) [Monotonie von δ]≤ r ·OPT (w − δ) + r ·OPT (δ) [B’s Eigenschaft und δ r-effektiv]≤ r ·OPT (w) [Zerlegungsbeobachtung]

1Ist also B eine r-Approximation


2.4 2-Approximationen fur das gewichtete Knotenuberdeckungs-problem

Der Algorithmus von Bar-Yehuda und Even

Kante e definiert Gewichtsreduktionsfunktion δe durch

δe(v) ={

min{w(v1), w(v2)} , v ∈ e0 , v /∈ e

Aus ∀e ∈ E : δe = 0 folgt: ∀{v1, v2} ∈ E : w(v1) = 0 ∨ w(v2) = 0; d.h., dieausgegebene Menge C ist eine Knotenuberdeckung.

1. Rekursive Variante

BErec G = (V,E), w)

• Falls ∀e ∈ E : δe = 0, gib C = {v ∈ V | w(v) = 0} aus; exit.

• Nimm irgendeine Kante e = {v1, v2} aus G (mit δe 6= 0 );

• Berechne BErec (G, w − δe)

2. Iterative Variante

BEiter G = (V,E), w)

• Fur jedes e ∈ E

– Bestimme ε := min{w(v) | v ∈ e}.– Fur jedes v ∈ e setze w(v) := w(v)− ε.

• Gib C = {c ∈ V | w(v) = 0} aus.

Es ist leicht einzusehen, dass die iterative Variante dasselbe wie die rekursiveberechnet.

In dem hier diskutierten Fall von Graphen ist fur e = {v1, v2} ε = min{w(v1),w(v2)} und die Gewichtsreduktion ist dann w(v1) := w(v1)−ε sowie w(v2)) :=w(v2)−ε. Die etwas umstandlich-mathematisch wirkende Formulierung wur-de gewahlt, um auch Hypergraphen mit demselben Algorithmus weiter untenabhandeln zu konnen.

Wir zeigen die Arbeitsweise der rekursiven Variante des Algorithmus an un-serem kleinen Beispiel; die Gewichtsreduktionsfunktion δe ist an den Kantennotiert:


3

24

1

6 1 3

7

4

2 4

1

12

1 1

3

4

3

Die folgenden Bilder zeigen, wie sich nach und nach die Gewichtsfunktionverandert durch fortgesetzte rekursive Aufrufe. Die ausgewahlte Kante istdurch eine neue Farbe hervorgehoben. Die Knoten, die unser Algorithmusschließlich in die Knotenuberdeckung hineinfugen wird, sind in Magentaherausgestellt.

Erste Kantenwahl:

3

4

1

6 1 3

7

4

2 4

1

12

1 1

3

4

3

2 0

11

0

0

0

Zweite Kantenwahl:

3

4

1

6 1 3

7

4

2 4

1

12

1 1

3

4

3

2 0

11

0

0

0

00

02

2

Dritte Kantenwahl:

3

4

1

6 1 3

7

4

2

1

12

1 1

3

4

3

2 0

11

0

0

0

00

02

2

4 0 33

3

Vierte Kantenwahl:


3

4

1

6 1 3

7

4

2

1

12

1 1

3

4

3

0

11

0

0

0

00

02

2

4 0 33

3

0

0

0

1

2

2+4+7+1 +1+3 = 18

Die gewonne Losung enthalt eine inklusions-minimale mit Gewicht 14; diesekann mit einem Greedy-Algorithmus (als Nachverbesserung) gefunden wer-den.

3

24

1

6 1 3

7

4

2 4

1

12

1 1

3

4

3

Satz 2.3 Der Algorithmus von Bar-Yehuda und Even ist eine 2-Approximation.

Beweis: Wir beweisen jetzt die Behauptung durch Induktion uber die Re-kursionstiefe t von BErec:

• Ist t = 0 , so liefert BErec sogar eine optimale Losung.

• Ist die Behauptung, BErec liefere 2-Approximationen, fur t = 0, .., Tgezeigt, so liefert der Satz uber die lokalen Verhaltnisse den Induktions-schritt, denn δe ist 2-effektiv. Ist namlich Cδe eine optimal Uberdeckungfur δe, so wird insbesondere e = {v1, v2} abgedeckt, d.h.

δe(C∗δe

) ≥ min{w(v1), w(v2)};

andererseits ist naturlich

δe(V ) = δe(v1) + δe(v2) = 2 ·min{w(v1), w(v2)},

also δe(V ) ≤ 2 ·OPT (δe) .


Wie gut ist die gefundene Losung “wirklich” ?

Diese Frage enthalt ein wichtiges Problem beim “Benchmarking” (Leistungs-vergleich) heuristischer Algorithmen fur NP-harte Probleme. Hierbei sindauch Approximationen hilfreich, namlich durch “moglichst ungeschickte Wahl”im Algorithmusablauf.

In unserem Beispiel konnte man am Schluss auch eine Losung vom Gewicht21 erhalten haben (s.u.); eine kleinstmogliche Uberdeckung C∗ hat also Ge-wicht w(C∗) ≥ 11. Der von uns zunachst verfolgte Ablauf des Algorithmusliefert also einen besseren Wert als der Satz garantiert.

3

24

1

6 1 3

7

4

2 4

1

12

1 1

3

4

3

Versuchen Sie einmal nachzuvollziehen, in welcher Reihenfolge der Algorith-mus von Bar-Yehuda/Evens hier gearbeitet hat.

Der Algorithmus von Clarkson

Wir schicken einige Hilfsdefinitionen voraus:

• δe aus dem vorigen Algorithmus BErec

• N(v): Menge der Nachbarn von Knoten v (offene Nachbarschaft).

• d(v) sei der Grad (engl.: degree) des Knoten v, also: d(v) = |N(v)|.d′(v) = |N ′(v)| mit N ′(v) = {u ∈ N(v) | w(u) > 0} fur Graph mitKnotengewichten w

• ε(v) = w(v)d(v) , ε′(v) = w(v)

d′(v)

• Gewichtsreduktionsfunktionen:

δ(′)v (u) =

w(v) , u = v

ε(′)(v) , u ∈ N (′)(v)0 , sonst

1. Rekursive Variante

Crec (G = (V,E), w)


• Falls ∀e ∈ E, δe = 0, gib C = {c ∈ V | w(v) = 0} aus; exit.

• Suche Knoten v ∈ V , der ε′(v) minimiert2.

• Dieses v definiert Gewichtsreduktionsfunktion δv(u).

• Berechne Crec(G, w − δ′v).

2. Iterative Variante

Citer (G, (V,E), w)

• C := ∅• Solange E 6= ∅, tue

– Suche v ∈ V , der ε(v) minimiert.– Fur jeden Nachbarn u ∈ V von v setze w(u) := w(u)− ε(v).– Setze G := G− v.– Setze C := C ∪ {v}.

• Gib C aus.

Man uberlege sich, dass die iterative Variante das selbe wie die rekursiveliefert. Beachte hierzu: Bei Crec bleiben nullgewichtete Knoten unbeachtet(ε′), bei Citer werden sie bevorzugt geloscht.

Dass die rekursive eine 2-Approximation ist, folgt wiederum durch Induktionaus dem Satz uber lokale Verhaltnisse. Wesentlich ist noch zu zeigen, dassδv eine 2-effektive Gewichtsfunktion ist.

a) Gewichtsfunktion: Klar fur u /∈ N (′)[v] = N (′)(v) ∪ {v} (abgeschlosseneNachbarschaft).Ist u ∈ N (′)(v), so ist δ

(′)v (u) = w(v)

d(′)(v)≤ w(u)

d(′)(u)≤ w(u) aufgrund der

minimalen Wahl von v.

b) 2-effektiv:

δ(′)v (V ) = δ(′)

v (v) + δ(′)v (N (′)(v)) + δv(V −N (′)[v])

= w(v) +∣∣∣N (′)(v)

∣∣∣ w(v)d(′)(v)

+ 0

= 2 · w(v) = 2 ·OPT (δ(′)v )

Uberlegen Sie sich, wie der Algorithmus von Clarkson auf unserem Beispielarbeitet.

2d(v) sei der Grad des Knoten v


2.5 Randomisierte r-Approximation

Eine Wahrscheinlichkeitsverteilung auf dem Raum der Gewichtsreduktions-funktionen zu (X, f, w) heißt r-effektiv, falls

E(δ(X)) ≤ r · E(OPT (δ))3

Unter der Ausnutzung der Linearitat des Erwartungswertfunktionals lasstsich in volliger Analogie zum deterministischen Fall zeigen:

Satz 2.4 Satz uber lokale Verhaltnisse - Randomisierte Version

Betrachte dazu folgenden Grundalgorithmus (bei Verteilung F )A(X, f, w)

• Wahle δ : X → R+gemaß r-effektiver Verteilung F .

• Berechne durch B(X, f, w − δ) eine Uberdeckung C.

• Gib C aus.

Falls B eine Uberdeckung C liefert mit

E((w − δ)(C)) ≤ r · E(OPT (w − δ)),

dann gilt:E(w(C)) ≤ r ·OPT (w),

d.h. A liefert eine randomisierte r-Approximation.

Beispiel 2.5 RandomGreedyVC (G = (V,E), w)

• Setze C := {v ∈ V | w(v) = 0} und G := G− C.

• Solange E 6= ∅ :

– w :=(∑

v∈Vd(v)w(v)

)−1

– Wahle zufallig v ∈ V mit Wahrscheinlichkeit p(v) = d(d)w(v) · w.

– Setze C := C ∪ {v} und G := G− v.

• Gib C aus.3E ist Erwartungswert (bzgl. der angenommenen Verteilung)


Ergebnis unserer Analyse soll sein nachzuweisen, dass RandomGreedyVCeine randomisierte 2-Approximation fur v ist. Dazu waren die im folgendenskizzierten Schritte im einzelnen durchzufuhren:

1. Uberfuhre RandomGreedyVC in eine aquivalente rekursive Form.

2. Zeige die Behauptung durch vollstandige Induktion uber die Rekursi-onstiefe unter Benutzung der randomisierten Version des Satzes uberlokale Verhaltnisse.

3. Dazu ist zu klaren: Wie sieht die Wahrscheinlichkeitsverteilung aufdem Raum der Gewichtsreduktionsfunktion aus?Die Reduktionsfunktion4

δv(u) = w(u)δuv ={

w(v), u = v0, u 6= v

wird mit Wahrscheinlichkeit p(v) gezogen.∑

v∈V p(v) = 1 gilt nachDefinition von p(v).5

4. Zu zeigen bleibt: die Wahrscheinlichkeitsverteilung ist 2-effektiv.

a)E(OPT (δ)) = E(δ(C∗)) =

∑v∈V

δv(C∗) · p(v)

=∑v∈C∗

w(v)p(v) =∑v∈C∗

d(v) · w ≥ |E| · w

b)E(δ(V )) =

∑v∈V

w(v)p(v) =∑v∈V

d(v)w ≤ 2 · |E| · w

2.6 (∆-)Hitting-Set — eine weitere Anwendung der Satzeuber lokale Verhaltinisse

Ggb: Grundmenge U (”Universum“) von n Elementen e1, . . . , en und Men-gen S1, . . . , Sm ⊆ U

Ges: Kleinste Anzahl j von Elementen ei1 , . . . , eij , die alle Hyperkanten tref-fen, d.h. ∀ 1 ≤ k ≤ m ∃ 1 ≤ r ≤ j : eir ∈ Sk

Ist bekannt, dass ∀1 ≤ i ≤ m : |Si| ≤ ∆ fur eine Konstante ∆, so las-sen sich die Algorithmen von Bar-Yahuda, Clarkson und Random-Greedy

4Wie ublich bezeichnet δuv die Kroneckerfunktion.5 Alle ubrigen Gewichtsfunktionen werden mit Wahrscheinlichkeit 0 gezogen.


auch fur ∆-Hitting-Set lesen.Die genannten Algorithmen funktionieren naturlich auch fur die entspre-chenden gewichteten Varianten und liefern jeweils ∆-Approximationen.

Eine mogliche Anwendung sind automatische Diagnosesysteme. Dies erlauternwir naher auf den Folien.

Ein abstrakteres Beispiel:

Eine kleinste Uberdeckung in dem Beispiel ware:

Neben Approximationsalgorithmen mit Gutegarantien sind auch hier wie-der Heuristiken hilfreich, insbesondere solche, die in manchen Situationenbeweisbar eine bestmogliche Wahl treffen (Datenreduktionsregeln).

Datenreduktionsregeln

1. Kantendominierung: f ⊂ e. ; entferne e

2. Kleine Kanten: e = {v} ; v kommt ins HS; entferne e

3. Knotendominierung: Ein Knoten x heiße dominiert durch einen Kno-ten y, falls {e ∈ E | x ∈ e} ⊆ {e ∈ E | y ∈ e} ; entferne x

R. S. Garfinkel and G. L. Nemhauser. Integer Programming. John Wiley & Sons,1972.


Oft wiederentdeckt: K. Weihe (Zugnetzoptimierung), R. Niedermeier & P. Rossma-nith (param. HS, 2003)Auch: R. Reiter (Theory of Diagnosis ; HS Baume, 1987)

Knotendomination

Kantenregeln

Knotendomination

Kantenregeln


Knotendomination

Ein irreduzibles Beispiel

Ein Naherungsverfahren — ubersetzt von VC: N1− 3HS(G = (V,E), C)

• (Wende Reduktionsregeln an.)

• Falls E leer, gib C aus; exit.

• Nimm irgendeine “kleine Kante” e aus Gund berechne N1− 3HS(G− e, C ∪ e) (e aufgefasst als Knotenmenge)

Dies ist ein 3-Approximations-Verfahren.

Ein irreduzibles Beispiel wird approximiert:


Wie gut ist die Approximation “wirklich” ?

Faktor 3 ist nur schlimmster Fall ! Wir erreichen 5 Knoten-Losung mit dem “bana-len” Algorithmus.Da unser irreduzibles Beispiel das fruhere als Teilfall enthalt, wissen wir: 4 ist eineuntere Schranke. Am Lauf des Algorithmus sehen wir: zweimal haben wir zwei Kno-ten statt moglicherweise einem genommen, beim dritten Schritt waren wir optimal; untere Schranke 3 (auch ohne das fruher behandelte Teilproblem).; Der Satz uber lokale Verhaltnisse gestattet das Auffinden besserer Schranken imkonkreten Beispiel.Tatsachlich gibt es Losung mit 4 Knoten, und die findet unser Algorithmus “fast”.

1.3 Zusammenfassung und Ausblick

• Bisher kennen gelernte Naherungsalgorithmen sind oft sehr kurze Programmstucke

• Schwierigkeit: Analyse, betreffend die Gute der Naherung!

• Warum sind die Gutegarantien schwierig zu beweisen?Grundsatzlich (und intuitiv) lasst sich dies genau so begrunden wie die ver-mutete Ungleichheit von P und NP.

Das sehen wir am Beispiel des Knotenuberdeckungsproblems:

+ Es ist leicht, eine vorgegebene Losung insofern zu verifizieren, als dass die Kno-tenuberdeckungseigenschaft uberpruft wird.

- Es ist schwierig nachzuweisen, dass eine gefundene Knotenuberdeckung kleinstmoglich(optimal) ist.

Konkret: Betrachten Sie den Petersen-Graph.


Konnen Sie (mit Hilfe unserer bisherigen Betrachtungen) begrunden, weshalb einekleinstmogliche Knotenuberdeckung wenigstens 5 Knoten enthalt?Schwieriger noch: Benutzen Sie den Satz uber lokale Verhaltnisse, um nachzuweisen,dass wenigstens 6 Knoten in jeder Knotenuberdeckung des Petersen-Graphen zufinden sind. (Hinweis: 5

3 -Approximation fur Kreise der Lange 5!)

In den folgenden Kapiteln erwartet Sie ein systematisches Kennenlernen verschie-dener Techniken zum Entwurf und zur Analyse von Naherungsalgorithmen.

3 GRUNDLEGENDE DEFINITIONEN 29

3 Grundlegende Definitionen

3.1 Spezifikation von Optimierungsproblemen

Wir wollen zunachst einen einfachen Formalismus zur Spezifizierung von Optimie-rungsproblemen kennen lernen.

Definition 3.1 Ein Optimierungsproblem P wird beschrieben durch ein Quadrupel(IP , SP ,mP , optP), wobei

1. IP die Menge der moglichen Eingaben (Instanzen),

2. SP : IP → Menge der zulassigen Losungen (engl.: feasible solutions),

3. mP : (x, y) 7→ mP(x, y) ∈ N (oder Q, ...) fur x ∈ IP , y ∈ SP(x) liefert denWert der zulassigen Losung y und

4. optP ∈ {min,max} gibt an, ob P ein Minimierungs- oder Maximierungspro-blem ist.

IP und SP(x) sind –geeignet codierte– formale Sprachen uber dem Alphabet {0, 1}.

Weitere Bezeichnungen

S∗P : IP → Menge der optimalen Losungen, d.h.

∀x ∈ IP ∀y∗(x) ∈ S∗P(x) : mP(x, y∗(x)) = optP{mP(x, z) | z ∈ SP(x)}.

Der Wert einer optimalen Losung wird auch m∗P(x) notiert.

Ist P aus dem Zusammenhang klar, so schreiben wir kurz –unter Fortlassung desIndexes P— I, S,m, opt, S∗,m∗.

3.2 Problemvarianten

Konstruktionsproblem (construction problem):

PC : Ggb. x ∈ IP , liefere ein y∗(x) ∈ S∗P(x) sowie ihren Wert m∗P(x)

Auswertungsproblem (evaluation problem):

PE : Ggb. x ∈ IP , liefere m∗P(x)

Entscheidungsproblem (decision problem):

PD : Ggb. x ∈ IP und Parameter k ∈ N, entscheide ob

m∗P(x) ≥ k, (falls optP = max)

bzw. ob

m∗P(x) ≤ k, (falls optP = min).


Beispiel 3.2 Knotenuberdeckungsproblem VC

1. I = {G = (V,E) | G ist Graph }2. S(G) = {U ⊆ V | ∀{x, y} ∈ E : x ∈ U ∨ y ∈ U}

(Knotenuberdeckungseigenschaft)

3. m = |U |4. opt = min

V CD ist dann das entsprechende ”parametrisierte Problem“, d.h. ggb. Graph G =(V,E) und Parameter k, gibt es eine Knoteuberdeckung U ⊆ V mit |U | ≤ k?

3.3 Die Klassen PO und NPO

Definition 3.3 P = (I, S,m, opt) gehort zu NPO, gdw:

1. x?∈ I ist in Polynomzeit entscheidbar.

2. Es gibt ein Polynom q derart, dass ∀x ∈ I ∀y ∈ S(x) : |y| ≤ q(|x|) und fur

alle y mit |y| ≤ q(|x|) ist die Frage y?∈ S(x) in Polynomzeit entscheidbar.

3. m ist in Polynomzeit berechenbar.

Beispiel VC: zu Punkt 2: Jede Knotenuberdeckung ist in ihrer Große trivialerweisedurch die Machtigkeit der Knotenmenge beschrankt.

Satz 3.4 Ist P ∈ NPO, so ist PD ∈ NP.

Beweis: (nur fur optP = max),PD lasst sich bei Eingabe von x ∈ I und k wie folgtlosen (in nichtdeterministischer Weise):

1. Rate y mit |y| ≤ q(|x|) in Zeit O(q(|x|)). (q(|x|) Bits sind zu raten)Dieser Schritt ist polynomiell wegen Eigenschaft 2 von NPO-Problemen.

2. Teste y ∈ S(x) in Polynomzeit.Dieser Schritt ist polynomiell wegen Eigenschaft 1 von NPO-Problemen.

3. Falls y ∈ S(x), berechne m(x, y) in Polynomzeit.Dieser Schritt ist polynomiell wegen Eigenschaft 3 von NPO-Problemen.

4. Falls y ∈ S(x) und m(x, y) ≤ k, antworte JA.

5. Falls y /∈ S(x) oder m(x, y) > k, antworte NEIN. 2

Definition 3.5 Ein Optimierungsproblem P gehort zur Klasse PO gdw. PC inPolynomzeit gelost werden kann.

Der nachstehende Satz 3.7 liefert eine Begrundung dafur, dass PO uber das zu-gehorige Konstruktionsproblem definiert ist: Das Konstruktionsproblem ist namlichdas Schwierigste unter den diskutierten Problemvarianten. D.h., wenn das Kon-struktionsproblem ”einfach“ ist, so sind erst recht die anderen Varianten einfach.


Erinnerung: (polynomielle) Turing-ReduzierbarkeitP1 ≤(p)

T P2 (in Worten: P1 ist reduzierbar auf P2) gdw.es gibt eine Turing-Maschine, die eine Instanz x von P1 (in Polynomzeit) mit Hilfevon Orakelanfragen (das sind generierte Instanzen von P2, die auf ein ”Orakelband“geschrieben werden und gedachter Weise in konstanter Zeit beantwortet werden)bearbeiten kann.Hinweis: In einer einfuhrenden Vorlesung zur Komplexitatstheorie wird vornehmlichauf den Spezialfall der many-one-Reduzierbarkeit eingegangen, bei der insbesonderenur ein Orakelaufruf moglich ist.

Wir werden uns in dieser Vorlesung vornehmlich um kombinatorisch harte Proble-me kummern, fur die kein (deterministischer) Polynomzeitalgorithmus bekannt ist.Daher ist die polynomielle Turing-Reduzierbarkeit ≤p

T in diesem Abschnitt der furuns adaquate Begriff. Wir schreiben P1 ≡p

T P2, falls sowohl P1 ≤pT P2 als auch

P2 ≤pT P1 gelten.

Da V C ∈ NPO und V CD NP-hart ist, erhalten wir:

Folgerung 3.6 P 6= NP→ PO 6= NPO.

Satz 3.7 ∀P ∈ NPO : PD ≡pT PE ≤p

T PC

Beweis: Klar: PD ≤pT PE ≤p

T PC .Z.z: PE ≤p

T PD.Dazu uberlegen wir uns:

{mP(x, y) | y ∈ SP(x)} ⊆ 0 . . . 2p(|x|) (1)

fur ein Polynom p.Dann kann PE durch binare Suche auf dem Intervall 0 . . . 2p(|x|) mit p(|x|) vielenOrakelanfragen an PD gelost werden.

Da P ∈ NPO, ist mP(x, y) in Zeit r(|x|, |y|) fur ein Polynom r berechenbar. Dasheißt insbesondere, dass

0 ≤ mP(x, y) ≤ 2r(|x|,|y|)

gilt. Da P ∈ NPO, ist |y| ≤ q(|x|) fur alle y ∈ SP(x) fur ein Polynom q. Daher giltfur das Polynom p(n) := r(n, q(n)) die Beziehung (1).

Im Folgenden wollen wir klaren, inwiefern bzw. wann auch PE und PC polynomiellTuring-aquivalent sind. Dazu diskutieren wir zunachst ein Beispiel.

3.4 MAXCLIQUE als Beispielproblem

Ein vollstandiger Graph mit n Knoten ist (isomorph zu, i.Z. ∼=)

Kn = ({1 . . . n}, {{i, j} | 1 ≤ i < j ≤ n}).


Eine Clique in einem Graphen ist eine Knotenteilmenge, die einen vollstandigenGraphen induziert. Das MAXCLIQUE-Problem fragt in einem Graphen nach großtmoglichen(maximum) Cliquen.

Unter Benutzung des oben eingefuhrten Formalismus zur Spezifizierung von Opti-mierungsproblemen stellt sich MAXCLIQUE wie folgt dar:

I : alle Graphen G = (V,E)S : alle Cliquen in G, d.h. U ⊆ V : G(U) ∼= K|U | (vollstandiger Graph mit |U |Knoten)m = |U |opt = max

Algorithmus fur MAXCLIQUEC ≤pT MAXCLIQUEE

Wir stellen einen einfachen Algorithmus, MAXCLIQUEEC (G), vor, der MAXCLIQUEC ≤p

T

MAXCLIQUEE zeigt:

Eingabe: Graph G = (V,E)

Ausgabe: eine großtmogliche Clique in G

begin

k := MAXCLIQUEE(G);

Falls k = 1 liefere irgendeinen Knoten in V

sonst finde Knoten v ∈ V mit k = MAXCLIQUEE(G(N [v]))

und liefere {v} ∪MAXCLIQUEEC (G(N(v))).6

Warum ist das Programm korrekt?

• Die Auswahl ”v ∈ V mit k = MCE(G(N [v]))“ garantiert, dass v in einergroßtmoglichen Clique liegt.

• Es ist klar, dass G(N(v)) eine Clique (evtl. mehrere) der Große k− 1 enthalt(und auch keine großere); eine dieser wird rekursiv gefunden.

Zeitkomplexitat des Algorithmus (n = # Knoten):

T (1) = O(1)T (n) = (n + 1) + T (n− 1)

↪→ Durchsuchen des Graphen= (n + 1) + n + . . . + n + O(1) = O(n2)

Gilt ”das“ auch allgemein? Der Schlussel dazu ist die NP-Harte des Entscheidungs-problems MAXCLIQUED, wie der folgende Satz lehrt.


Satz 3.8 Ist P ∈ NPO und ist PD NP-hart, so gilt: PC ≤T PD.

Beweis: (fur optP = max).Im Beweisgang werden wir ein anderes NPO-Problem P ′ konstruieren mit PC ≤p

T

P ′E . Wegen Satz 3.4 liegt P ′D in NP, und PD ist nach Voraussetzung NP-hart, alsogilt

P ′E ≤pT P

′D ≤

pT PD

wegen Satz 3.7, und die Transitivitat der Reduktionsrelation liefert die Behauptung.P ′ ist wie P definiert mit Ausnahme des Messfunktion mP′ . Betrachte dazu einPolynom q mit ∀x ∈ IP ∀y ∈ SP(x), |y| ≤ q(|x|) (s. Definition NPO). Mit anderenWorten: SP(x) ⊆ {0, 1}≤q(|x|).

Setze nun τ(y) := 2q(|x|)−|y|y (Konkatenation!). Es gilt |τ(y)| = q(|x|). Fur jedesy ∈ SP(x) bezeichne λ(y) den Wert von τ(y), interpretiert als Ternarzahl. Darausfolgt: 0 ≤ λ(y) ≤ 3q(|x|).Außerdem gilt:∀y, y′ ∈ SP(x) : y = y′ ⇐⇒ τ(y) = τ(y′) ⇐⇒ λ(y) = λ(y′).Setze fur jedes x ∈ IP′ = IP und jedes y ∈ SP′(x) = SP(x) :

mP′(x, y) = 3q(|x|)+1mP(x, y) + λ(y).

Beachte: P ′ ∈ NPO, denn mP′ ist in Polynomzeit berechenbar, weil insbesonderedie Exponentiation 3q(|x|) nur O(q(|x|)) viele Bits benotigt.Damit: ∀x ∀y1, y2 ∈ SP′(x) : y1 6= y2 → mP′(x, y1) 6= mP′(x, y2).Also gibt es eine eindeutig bestimmte maximale zulassige Losung y∗P′(x) in S∗P′(x).Nach Definition von mP′ gilt ferner:

(mP′(x, y1) > mP′(x, y2)⇒ mP(x, y1) ≥ mP(x, y2)).

Daraus folgt: y∗P′(x) ∈ S∗P(x).y∗P′(x) kann wie folgt mit einem Orakel fur P ′E in Polynozeit berechnet werden.

1. Bestimme m∗P′(x) (Orakel!)

2. Berechne λ(y∗P′(x)) = m∗P′(x) mod (3q(|x|)+1 ·mP(x, y)).

Dies kann durch wiederholte Subtraktion von 3q(|x|)+1 geschehen; hochstenspolynomiell oft ist zu subtrahieren, da P in NPO liegt und deshalb —wie wiruns schon fruher uberlegten— mP(x, y) durch ein Polynom in |x| beschranktist.

3. Bestimme y aus λ(y).

Daher kann PC mit einem Orakel fur P ′E in Polynomzeit berechnet werden, dennm∗P(x) = mP(x, y) fur das mit oben stehendem Algorithmus berechnete y.


Grundtechniken

In diesem Teil des Skriptums soll es darum gehen, gewisse Grundtechniken desEntwurfs von Naherungsalgorithmen systematisch zu studieren.

Man beachte wiederum:

• Die dikutierten Verfahren sind sehr einfach (zu implementieren).

• Es ist leicht einzusehen, dass sie stets eine zulassige Losung liefern.

• Schwierig bleibt der Nachweis der Gute der Naherung.

Die einzelnen Abschnitte widmen sich dabei:

• Greedy-Verfahren

• Partitionsprobleme

• Lokale Suche

• Lineares Programmieren

• Dynamisches Programmieren

4 GREEDY-VERFAHREN 35

4 Greedy-Verfahren

Allgemeines zu Greedy-Verfahren; hier speziell bei Maximierungsverfahren:Allgemeine Aufgabe ist hierbei: Aus einer Grundmenge X ist eine maximale zulassigeLosung Smax zu finden.Greedy lasst sich (eventuell) einsetzen, falls die Menge der zulassigen Losungenmonoton ist in dem Sinne, dass, falls S zulassige Losung ist, so auch S′ ⊆ S fur alleS′ ⊆ S.Damit ist auch ∅ eine zulassige Losung, mit der das Verfahren starten kann. Greedy-Verfahren sortieren haufig zuerst die vorgebene Grundmenge nach einem geeignetenKriterium und gehen die so sortierte Liste sukzessive durch.Fur jedes Element x der Liste wird dabei fur die bislang gefundene zulassige LosungS′ gepruft, ob S′ ∪{x} ebenfalls zulassig ist. Wenn ja, wird S′ := S′ ∪{x} gebildet.Auf diese Weise ist garantiert, dass stets nur zulassige Losungen ausgegeben wer-den. Außerdem ist klar, dass eine so gefundene zulassige Losung S′ nicht mehrdurch Hinzunahme eines weiteren Elements x /∈ S′ erweitert werden kann, dennwenn {x} ∪ S′ zulassig ware, dann auch {x} ∪ S′′ fur alle S′′ ⊆ S′ aufgrund derMonotonie; speziell galte dies fur ein S′′, das als ”bisherige Losung“ an dem Punkt,als x untersucht wurde, gebildet worden war.

Analog kann man sich Geedy-Verfahren uberlegen fur die in Kapitel 1 besproche-nen Uberdeckungsprobleme, wobei man jetzt mit der Gesamtmenge X startet undsukzessive Elemente entfernt, sodass immer noch die Zulassigkeit (modelliert durchf(X ′) = 1 fur X ′ ⊆ X) gewahrleistet ist. Beispiel 4.15 (s.u.) zeigt eine alternativeGreedy-Strategie fur Minimierungsprobleme.

Wegen des Sortierschritts haben solche Greedy-Verfahren meist eine Zeitkomple-xitat von O(n log n).

4.1 Das Rucksackproblem

Beispiel 4.1 Maximum Knapsack (Rucksackproblem)

I: endliche Menge X bzw. ”Liste“ X = {x1, . . . , xn}Profitfunktion p : X → N bzw. ”Liste“ {p1, . . . , pn}Großenfunktion a : X → N bzw. ”Liste“ {a1, . . . an}Fassungsvermogen b ∈ N des Rucksacks[O.E.: ∀1 ≤ i ≤ n : ai ≤ b im Folgenden]

S: {Y ⊆ X | a(Y ) =∑

xi∈Y ai ≤ b}m: p(Y ) =

∑xi∈Y pi

opt: max

Mitteilung 4.2 Knapsack ist NP-vollstandig.

Heuristische Idee:Es ist gunstig, moglichst solche Sachen xi in den Rucksack zu tun, die moglichstviel Profit versprechen, gemessen am in Anspruch genommenen Platz.


; GreedyKnapsack (X, p, a, b)

1. Sortiere X absteigend nach dem Verhaltnis pi

ai.

({x1, . . . , xn} sei die erhaltene sortierte Grundmenge)

2. Y := ∅ (die leere Menge ist zulassig)

3. Fur i := 1 bis n tue:wenn ai ≤ b, dann Y := Y ∪ {xi}; b := b− ai.

4. Liefere Y zuruck.

Leider kann GreedyKnapsack beliebig schlechte Ergebnisse liefern, wie folgendesBeispiel lehrt:

p : {p1 = 1, . . . , pn−1 = 1, pn = b− 1}a : {a1 = 1, . . . , an−1 = 1, an = b = k · n} fur ein beliebig großes k ∈ N

Hier ist fur x = (X, p, a, b) : m∗(x) = b− 1 = k · n− 1 > kn− k = k(n− 1) (durchWahl des letzten Elements), aber GreedyKnapsack liefert, da

p1

a1= 1 = . . . =

pn−1

an−1>

pn

an=

b− 1b

mGreedy(x) =n−1∑i=1

pi = n− 1, d.h.m∗(x)

mGreedy(x)> k

Eine andere heuristische Idee furs Rucksackfullen ware, X einfach absteigend nachdem Profit zu sortieren. Nahezu dasselbe Beispiel wie eben (nur mit an = n

k ) lehrt,dass auch hier beliebig schlechte Losungen herauskommen konnen.

Der entsprechende Algorithmus GreedyKnapsack’(X, p, a, b) arbeitet genau so wieGreedyKnapsack, nur dass die erste Zeile durch

1. Sortiere X absteigend nach dem Profit pi.

zu andern ist.Erstaunlicherweise hat der folgende Kombinationsalgorithmus eine Gutegarantie:

; GreedyKnapsackKombi(X, p, a, b)

1. Y1 := GreedyKnapsack (X, p, a, b)

2. Y2 := GreedyKnapsack’(X, p, a, b)

3. Wenn p(Y1) ≥ p(Y2), dann liefere Y1, sonst liefere Y2.

Tatsachlich werden wir im Folgenden auf eine leicht variierte Version der Kombi-nation der beiden heuristischen Ideen eingehen, namlich auf:

GreedyKnapsack”(X, p, a, b)Dieser Algorithmus arbeitet wie GreedyKnapsack, nur dass Schritt 4 ersetzt wirddurch


4.” Suche xmax mit ∀i : pi ≤ pmax (maximaler Profit!)

5.” Wenn p(Y ) ≥ pmax, dann liefere Y sonst liefere {xmax}.

Lemma 4.3 Fur alle Instanzen x gilt:

mGreedyKnapsack′′(x) ≤ mGreedyKnapsackKombi(x)

Damit ubertragt man die im folgenden Satz gezeigte Gutegarantie von Greedy-Knapsack” auf GreedyKnapsackKombi.Abkurzend schreiben wir mG,mG′′ fur mGreedyKnapsack bzw. mGreedyKnapsack′′ .

Satz 4.4 Ist x eine MaximumKnapsack-Instanz, so ist

m∗(x)mG′′(x)

< 2.

Beweis: Es sei j der Index des ersten Elements, welches der Greedy-AlgorithmusGreedyKnapsack nicht in den Rucksack tut.Es gilt:

pj :=j−1∑i=1

pi ≤ mG(x) ≤ mG′′(x).

Ferner setzen wir:

aj :=j−1∑i=1

ai ≤ b.

Behauptung: m∗(x) < pj + pj .

Aus der Behauptung folgt die Aussage des Satzes, denn:

• Gilt pj ≤ pj , so ist m∗(x) < 2pj ≤ 2mG(x) ≤ 2mG′′(x).

• Gilt pj > pj , so ist m∗(x) < 2pj ≤ 2pmax ≤ 2mG′′(x).

Warum gilt die Behauptung? Betrachte (kurzfristig) die folgende Verallgemeinerungdes Rucksackproblems: Es sei nun erlaubt, ”Bruchstucke“ der xi (mit entsprechendder Große skaliertem Gewinn) in den Rucksack zu tun. Der Wert einer optimalenLosung fur das neue Problem ist sicher eine obere Schranke fur m∗(x). Wie manleicht einsieht, ist

pj + (b− aj) ·pj

aj

der maximale Wert einer Losung des variierten Problems, wenn die xi nach pi

ai

absteigend sortiert vorliegen und j wie oben definiert ist.

⇒ m∗(x) ≤ pj + (b− aj)︸︷︷︸<aj

·pj

aj< pj + pj .


Bemerkung 4.5 Tatsachlich liefert Satz 4.4, dass der folgende Algorithmus eine12 -Approximation von Maximum Knapsack ist:

1. Sortiere X absteigend nach pi

ai.

2. Y := ∅; i := 1;

3. Solange i ≤ n und ai ≤ b, tue:Y := Y ∪ {xi}; b := b− ai; i := i + 1.

4. Wenn ai ≤ b,7 dann liefere Y ,sonst, wenn pi ≤ p(Y ), dann liefere Y ,

sonst liefere {xi}.

Hinweis: Verallgemeinerung von Problemen ist oft ein Ansatz, um Schranken furApproximationsgute zu gewinnen.

Bemerkung 4.6 Es gibt eigene Bucher zum Thema ”Rucksackprobleme“, z.B. S.Martello, P. Toth: Knapsack Problems; Algorithms and Computer Implementations,Wiley, 1990.

4.2 Unabhangige Mengen in Graphen

Beispiel 4.7 Maximum Independent Set (MIS)

I: Graph G = (V,E)S: {U ⊆ V | E(G[U ]) = ∅}︸︷︷︸

”unabh. Menge“m: |U |opt: max

Mitteilung 4.8 MISD ist NP-vollstandig.

Heuristische Idee:Es ist gunstig, moglichst kleingradige Knoten zu wahlen.

; GreedyIndependantSet(G = (V,E)):

1. Setze U := ∅; V ′ := V.

2. Solange V ′ 6= ∅, tue:

2a: x sei Knoten kleinsten Grades in G(V ′).

2b: U := U ∪ {x}7 D.h., wenn i = n + 1, also Y = X.


2c: V ′ := V ′ \N [x].

3. Liefere U

Der Greedy-Algorithmus kann beliebig schlechte Ergebnisse liefern, wie folgendesBeispiel lehrt.

Beispiel 4.9 Betrachte die folgenden Graphenschar: Gk

V (Gk) = {v1, . . . , vk, u1, . . . , uk, w}.G({v1, . . . , vk}) = Kk. Weitere Kanten: {{vi, uj}, {ui, w} | 1 ≤ i, j ≤ k}⇒ E(G({u1, . . . , uk})) = ∅.GreedyIndependentSet liefert aber w als kleinstgradigen Knoten und einen der Kno-ten vi, also nur zwei Knoten als unabhangige Menge, wahrend es doch (wie beschrie-ben) unabhangige Mengen der Große k gibt.

Bemerkung 4.10 Falls P 6= NP , so gibt es nachweislich keinen guten Naherungsalgorithmusfur alle Graphen.Daher betrachten wir im folgenden speziellere Graphklassen, namlich solche vonbeschrankter Dichte (dem Verhaltinis von Kanten- zu Knotenzahl). Aus der Euler-formel folgt, dass planare Graphen eine durch 6 beschrankte Dichte haben.

Mathematischer Exkurs

Lemma 4.11 Betrachte x1, . . . , xn ≥ 0; setze x =P

xi

n . Dann gilt:∑xi

2 ≥ n · x2

Beweis: Fur ∆i := xi − x gilt∑∆i =

∑(xi − x) =

∑xi − n · x = 0

;∑

xi2 =

∑(x + ∆i)

2 =∑

x2 + 2x∑

∆i︸︷︷︸=0

+∑

∆2i ≥

∑x2 = n · x2


Lemma 4.12 ∀x, y > 0 : xy + y

x ≥ 2

Beweis:

x

y+

y

x=

x2 + y2

x · yL 4.11≥

2 · (x+y2 )2

x · y=

(x + y)2

2xy=

x2 + 2xy + y2

2xy=

12

(x

y+

y

x

)+ 1

Satz 4.13 Es sei G ein Graph mit n Knoten und m Kanten. Es bezeichne δ = mn

seine Dichte. Der Wert mGr(G), den GreedyIndependentSet(G) liefert, ist wenig-stens n

2δ+1 .

Beweis: Es sei xi der in der i-ten Iteration der Solange-Schleife in Schritt 2aausgewahlten Knoten und di bezeichne den Grad von xi. In Schritt 2c werden xi

und seine Nachbarn entfernt, d.h. insgesamt di + 1 viele Knoten. Dadurch werdenwenigstens di(di+1)

2 viele Kanten entfernt, denn

• xi ist ein Knoten minimalen Grades im aktuellen Graphen und

• von jedem der insgesamt di + 1 vielen entfernten Knoten gehen insgesamtwenigstens di(di + 1) viele (nicht notwendig verschiedene) Kanten aus; imschlimmsten Fall —wenn namlich jeder der di + 1 Knoten aus der Nachbar-schaft N [xi] mit jedem anderen Knoten aus N [xi] verbunden ist und sonstmit keinem anderen Knoten außerhalb von N [xi]— sind es di(di+1)

2 viele ver-schiedene Kanten.

Wenn wir uber alle mGr(G) viele Iterationen des Programmes aufsummieren, er-halten wir

(1)∑mGr(G)

i=1di(di+1)

2 ≤ m = δ · n.Beachte: Es gilt i.a. ”≤“ nicht ”=“, da di(di+1)

2 nur eine untere Schranke derAnzahl der im i-ten Schritt entfernten Kanten ist.

Da der Algorithmus halt, wenn alle Knoten entfernt worden sind, gilt außerdem:

(2)∑mGr(G)

i=1 (di + 1) = n.

Addieren wir (2) und (zweimal) (1), so bekommen wir:

mGr(G)∑i=1

(di + 1)2 ≤ n(2δ + 1).

Der Mittelwert der (di + 1) ist∑(di + 1)

mGr(G)(2)=

n

mGr(G)


und Lemma 4.11 liefert damit

n(2δ + 1) ≥∑

(di + 1)2 ≥ mGr(G) · n2

(mGr(G))2=

n2

mGr(G).

Also gilt:mGr(G) ≥ n

2δ + 1.

2

Satz 4.14 Es sei G ein Graph mit n Knoten und m Kanten. Setze δ = mn . Der

Wert mGr(G), den GreedyIndependentSet(G) liefert, genugt

m∗(G)mGr(G)

≤ δ + 1

Die folgenden Bezeichnungen lehnen sich an die des vorigen Beweises an.Beweis: Es sei V ∗ eine großtmogliche unabhangige Menge. Es bezeichne ki dieAnzahl der Knoten am V ∗, die unter den di + 1 im i-ten Schritt des Algorithmusentfernten Knoten sind. Naturlich gilt jetzt:

(3)∑mGr(G)

i=1 ki = |V ∗| = m∗(G)

Wir wollen jetzt Abschatzung (1) verbessern.Per Definition sind alle Knoten einer unabhangigen Menge nicht untereinanderverbunden. Daher gehen nicht nur di(di+1)

2 viele paarweise verschiedene Kantenmindestens von Knoten in N [xi] aus, sondern noch ”zusatzlich“ wenigstens ki(ki−1)

2viele, was

(1’)∑mGr(G)

i=1di(di+1)+ki(ki−1)

2 ≤ δn

liefert.

Jetzt addieren wir (2), (3) und (zweimal) (1’), um

mgr(G)∑i=1

(di + 1)2 +mGr(G)∑

i=1

k2i ≤ n(2δ + 1) + m∗(G)

zu erhalten. Der Mittelwert der (di + 1) ist nmGr(G) und der der ki ist∑

ki

mGr(G)=

m∗(G)mGr(G)

,

sodass jetzt Lemma 4.11

n(2δ + 1) + m∗(G) ≥ n2 + (m∗(G))2

mGr(G)


ergibt. Also ist:

mGr(G) ≥ n2 + (m∗(G))2

n(2δ + 1) + m∗(G)= m∗(G) ·

( nm∗(G) ) + (m∗(G)

n )

2δ + 1 + (m∗(G)n )

m∗(G)≤n u. L 4.12

≥ m∗(G) · 22δ + 1 + n

n

= m∗(G) · 1δ + 1

.

2

Bemerkungen zu MIS und verwandten Problemen

1. Fur manche Graphenklassen, z.B. die der Baume, liefert GreedyIndependent-Set stets eine optimale Losung. Man sieht also, dass die genaue Spezifikationder Klasse I zulassiger Instanzen wichtig ist.

2. GreedyIndependentSet enthalt in Schritt 2 einen gewissen (durch beliebi-ge Wahl aufgelosten) Nichtdeterminismus. Selbst, wenn man fur Graphenweiß, dass es eine Wahlmoglichkeit in Schritt 2a gibt, sodass seine Variantevon GreedyIndependentSet fur diese Graphen die optimale Losung findet,ist das auf solche Graphen eingeschrankte MISD-Problem (immer noch) NP-vollstandig.Literatur fur 1. und 2.: H. L. Bodlaender, D. M. Thilikos, K. Yamazaki: It ishard to know when greedy is good for finding independent sets. InformationProcessing Letters 61 (1997), 101–106.

3. Das Auffinden maximaler Cliquen in einem Graphen (MaxClique) ist genausoschwer —auch im approximativen Sinne— wie das Auffinden großtmoglicherunabhangiger Mengen, denn C ⊆ V ist maximale Clique in G = (V,E)genau dann, wenn C großtmogliche unabhangige Menge in Gc = (V,Ec) ist,Ec = {{v, v′} | v, v′, v ∈ V, v 6= v′, {v, v′} /∈ E}. Direkt implementiert ist dieheuristische Idee fur MaxClique, moglichst großgradige Knoten zu wahlen.

4. Unser Approximationsalgorithmus liefert fur die Klasse Gd der Graphen mitMaximalgrad d eine unabhangige Menge der Mindestgroße n

d+1 . Der ”Rest-graph“ hat Maximalgrad d − 1 (denn sonst konnte man den Knoten mitGrad d noch in die unabhangige Menge nehmen, da keiner seiner Nachbarnin diese Menge hinzugenommen wurde!), sodass sich auf ihn wiederum derApproximationsalgorithmus anwenden ließe. Auf diese Weise kann man eine(d + 1)-Farbung des Ursprungsgraphen erzeugen.

4.3 Das Handelsreisendenproblem

Bislang haben wir Beispiele fur Greedy-Algorithmen zu Maximierungsproblemenuntersucht. Jetzt wollen wir die Technik auch auf Minimierungsprobleme anwenden.

Beispiel 4.15 Minimum Traveling Salesperson MTS.(Handelsreisendenproblem)


I : vollstandiger gerichteter Graph G = (V,E), V = {v1, . . . , vn} mit posi-tiven Kantengewichten. (Abstandsfunktion; D(vi, vj)-Matrix uber Q+)

S : {(vi1 , . . . vin) ∈ V n | [∀j = 1, . . . , n− 1 : (vij , vij+1) ∈ E∧](i1, . . . , in) ist Permutation von (1, . . . , n)}↪→ alternative Schreibweise: Wort der Lange n uber V

m : D(vi1 , . . . vin) =∑n−1

j=1 D(vij , vij+1) + D(vin , vi1)(”Lange der Tour“)

opt: min

MTS ist sehr beliebt und popular. G.Reinelt, The Traveling Salesman, Computa-tional Solutions for TSP Applications, LNCS 840, 1994, ist ganz MTS ”gewidmet“.

Ein kleines Beispiel:

Ein optimaler Reiseweg eines Handlungsreisenden durch die 15 großten StadteDeutschlands ist gesucht. Der angegebene Weg ist der kurzeste unter 43 589 145600 moglichen.

Spezialfall: metrisches MTS (kurz: MMTS), d.h. D ist Metrik, also:

• ∀u, v : D(u, v) = D(v, u) (also ”ungerichteter Graph“)

• ∀u, v, w : D(u, w) ≤ D(u, v) + D(v, w) (4-Ungleichung)

• ∀u, v : D(u, v) = 0⇔ u = v

Bemerkung 4.16 Aus der 4-Ungleichung folgt unmittelbar:Ist f ′ = (vij1

, . . . , vijk) eine Teilfolge von f = (vi1 , . . . , vin),

so gilt D(f ′) ≤ D(f).

Mitteilung 4.17 MTSD und MMTSD sind NP-vollstandig.

Fur diesen Spezialfall analysieren wir folgenden Algorithmus MMTSNN :8

MMTSNN (G = (V,E), D)

1. Setze P := v fur irgendein v ∈ V und Pend := v.

8NN steht fur”nachster Nachbar“.


2. Setze V ′ := V \ {v}.

3. Solange V ′ 6= ∅ tue:

3a. v sei ein Knoten aus V ′, sodass∀u ∈ V ′ : D(Pend, v) ≤ D(Pend, u)

3b. Pend := v; P := P · Pend.[· steht fur die Konkatenation.]

3c. V ′ := V ′ \ {v}.

4. Liefere P .

Bezeichnung: Fur eine Tour f ∈ V ∗ sei

E(f) = {(u, v) ∈ V 2 | ∃x, z ∈ V ∗ : f = xu · vz oder f = vxu}.

Dann ist D(f) = D(E(f)).

Durch die Verwaltung der Menge V ′ ist klar, dass P ein zu keinem Zeitpunktzweimal den selben Knoten beinhaltet. M.a.W: das zuruckgelieferte P ist in jedemFall zulassig. Als Gutegarantie wollen wir den folgenden Satz beweisen:

Satz 4.18 Es sei (G = (V,E), D) eine Instanz von MMTS, |V | = n. Ist mNN (G, D)die Losung der von MMTSNN (G, D) gelieferten Tour, so gilt:

mNN (G, D)m∗(G, D)

≤ 12(dlog ne+ 1).

Satz 4.18 folgt sofort aus nachfolgendem Lemma (wegen der 4-Ungleichung), wennwir fur die von MMTSNN gelieferte Tour P = vi1 , . . . vin

festlegen,

l(vij ) ={

D(vij, vij+1), 1 ≤ j < n,

D(vin , vi1), j = n.

Augenscheinlich ist

mNN (G, D) =n∑

j=1

l(vj)

Lemma 4.19 Es sei (G, D) eine Instanz von MMTS, und sei G = (V,E), n = |V |.Existiert eine Abbildung l : V → Q mit

1. ∀u, v ∈ V, u 6= v : D(u, v) ≥ min(l(u), l(v))

2. ∀v ∈ V : l(v) ≤ 12m∗(G, D),

so gilt: ∑v∈V

l(v) ≤ 12(dlog ne+ 1) ·m∗(G, D)


Beweis: Es seien v1, . . . , vn absteigend gemaß ihrer l-Werte sortiert. Wir beweisenzunachst, dass m∗(G, D) ≥ 2 ·

∑min(2k,n)i=k+1 l(vi) fur alle 1 ≤ k ≤ n gilt. Dazu sei

P ∗ eine optimale Tour der Lange m∗(G, D). Betrachte die Teilmenge Vk = {vi |1 ≤ i ≤ min(2k, n)} von V . Bezeichne Pk diejenige Teiltour von P ∗, die entsteht,wenn man nur die ”Stadte“ aus Vk in der durch P ∗ vorgegebenen Reihenfolgedurchlauft. Wegen obiger Bemerkung ist D(Pk) ≤ D(P ∗) = m∗(G, D). Wegen derersten Voraussetzung gilt ferner:

D(Pk) ≥∑

(u,v)∈E(Pk)

min(l(u), l(v)) =∑

vi∈Vk

αil(vi)

fur gewisse αi ∈ {0, 1, 2}. Genauer gilt:

αi = |{vj ∈ Vk | {vi, vj} ∈ E ∧ j < i}| ,

denn die Vi werden als absteigend sortiert angenommen.Außerdem ist ∑

vi∈Vk

αi = |Vk| ≤ 2k.

Wegen der absteigenden Sortierung der vi konnen wir

∑vi∈Vk

αil(vi) ≥ 2 ·min(2k,n)∑

i=k+1

l(vi)

abschatzen, indem wir

α1 = . . . = αk = 0 und αk+1 = . . . = αmin(2k,n) = 2

annehmen. Damit ist

m∗(G, D) ≥ D(Pk) ≥ 2 ·min(2k,n)∑

i=k+1

l(vi)

gezeigt.Summieren wir diese Ungleichung fur k = 2j , j = 0, . . . , dlog ne−1, so erhalten wir:

dlog nem∗(G, D) =dlog ne−1∑

j=0

m∗(G, D) ≥dlog ne−1∑

j=0

2 ·min(2j+1,n)∑

i=2j+1

l(vi)

= 2 ·

n∑i=2

l(vi)

Mit der zweiten Voraussetzung, aus der m∗(G, D) ≥ 2 · l(v1) folgt, ergibt sich dieBehauptung des Lemmas. 2

Warum durfen wir das Lemma anwenden, um Satz 4.18 zu zeigen?Zu Voraussetzung 1: Es seien vij

, vikzwei Stadte der von MMTSNN gelieferten

Tour. Ist j < k; dann ist l(vij ) = D(vij , vij+1) ≤ D(vij , vik), denn sonst ware vik

statt vij+1 vom Algorithmus MMTSNN gewahlt worden. Ist j > k, dann gilt analog

l(vik) = D(vik

, vik+1) ≤ D(vik, vij ).


Zu Voraussetzung 2: Betrachte einen Knoten v ∈ V . Nach Definition von l gibt eseinen ”benachbarten“ Knoten u ∈ V auf der MMTSNN -Tour mit l(v) = D(u, v).Gemaß einer optimalen Tour P ∗ gibt es zwischen u und v zwei disjunkte Wege; jederdieser Wege hat wegen der 4-Ungleichung mindestens die Lange D(u, v). Daher ist

m∗(G, D) = D(P ∗) ≥ 2 ·D(u, v) = 2 · l(v).

Bemerkung 4.20 Logarithmische, nicht konstante Approximationsgute!Spater (Kap. 11 besser!

Die Popularitat von TSP ermisst sich leicht im Internet.Oft werden hierfur auch Metaheuristiken getestet, wie genetische Algorithmen.

http://fbim.fh-regensburg.de/~saj39122/vhb/NN-Script/script/gen/k040401.html

5 PARTITIONSPROBLEME 47

5 Partitionsprobleme

Bei einem Partitionsproblem ist im Allgemeinen eine Liste von Gegenstanden L ={x1, . . . , xn} gegeben, die Menge L ist so zu unterteilen, dass den problemspezifi-schen Einschrankungen Genuge getan ist; die entsprechende Partition wird ausge-geben. Ein allgemeines Schema einer (Greedy-)Heuristik fur Partitionsprobleme istdas Folgende:

1. Sortiere L (gemaß eines problemspezifischen Kriteriums)Sei (x1, . . . , xn) die sortierte Liste.

2. P := {{x1}};

3. Fur i = 2 bis n tueFalls xi zu einer Menge p aus P hinzugefugt werden kann

(gemaß einem problemabhangigen Kriterium),so fuge xi zu p hinzu

sonst P := P ∪ {{xi}}.

4. Liefere P zuruck.

In obigem Schema werden die Gegenstande der Liste der Reihe nach abgearbeitet;einmal getroffene Entscheidungen werden spater nie revidiert.

5.1 Scheduling

Beispiel 5.1 Scheduling auf identischen Maschinen (MSIM)

I : Menge von Tasks T , Anzahl p der identischen Maschinen,Dauer lj der Ausfuhrung von Task tj ∈ T(Tasks sind nicht unterbrechbar!)

S : {f : T → {1, . . . , p}} (oder: Partition P = {m1, . . . ,mp},⋃p

i=1 mi = T )m : Gesamtausfuhrungszeit von T : m(f) = max{

∑tj∈T,f(tj)=i lj | 1 ≤ i ≤ p}

opt : min.

Bemerkung 5.2 Historischer Ausgangspunkt fur Naherungsalgorithmen: Graham1969, vgl. das 1. und 2. Kapitel im Buch von Hochbaum!

List-Scheduling:

Heuristische Idee: Gib den nachsten Task an die Maschine, die mit ihrer bisherigenArbeit am schnellsten fertig ist.


Satz 5.3 Ist x = (T, p, l) eine Instanz von MSIM, so findet LS eine Naherungs-losung vom Wert mLS(x) (unabhangig von der Ordnung von T ), welche

mLS(x)/m∗(x) ≤ (2− 1p)

erfullt.

Beweis: Es sei T = {t1, . . . , tn}.Setze W :=

∑nk=1 lk. Klar: m∗(x) ≥W/p.

Wir nehmen an, LS habe bereits j Tasks zugewiesen. Bezeichne jetzt Ai(j) die Zeit,die notwendig ist, um die davor der Maschine i zugewiesenen Tasks zu beenden,d.h.

Ai(j) =∑

1≤k<j,f(tk)=i

lk

fur das von LS konstruierte Schedule f .Sei h eine Maschine mit Ah(n + 1) = mLS(x) und sei j der Index des Tasks, derals letztes h zugewiesen wurde. tj wurde von LS einer Maschine mit minimalerAuslastung zugewiesen, d.h.

∀1 ≤ i ≤ p : Ai(n + 1) ≥ Ai(j) ≥ Ah(j) = Ah(n + 1)− lj .

Damit gilt:

W =p∑

i=1

Ai(n+1) ≥ (p−1) · (Ah(n+1)− lj)+Ah(n+1) = p · (Ah(n+1)− lj)+ lj .

Also gilt:

mLS(x) = Ah(n + 1) ≤ W

p+

(p− 1)ljp

.

Wegen m∗(x) ≥W/p und m∗(x) ≥ lj folgt

mLS(x) ≤ m∗(x)+p− 1

pm∗(x) =

(2− 1

p

)m∗(x), denn m∗(x) ≥ max{W/p, lj} 2

Die in Satz 5.3 angegebene Schranke ist scharf, wie das folgende Beispiel lehrt!

Beispiel 5.4 Ggb: p. Betrachte die Instanz von MSIM mit p2−p Tasks der Lange1 und einem Task der Lange p, zu verteilen auf p Maschinen. Optimal ware es, diep(p−1) kurzen Tasks auf p−1 Maschinen zu verteilen und den großen Task auf dieverbleibende. Der optimale Wert ware also gleich p, denn ein Gesamtarbeitsvolumenvon p2 benotigt auf p Maschinen wenigstens p Schritte.

Wenn der große Task jedoch der letzte der Liste ist, werden zunachst die p(p − 1)kleinen Tasks gleichmaßig auf die p Maschinen verteilt, und dann bekommt irgend-eine der Maschinen noch weitere p Schritte Arbeit, namlich durch den großen Task.Daher liefert List Scheduling dann eine Losung vom Wert 2p− 1.


Bemerkung 5.5 List Scheduling lieferte im vorigen Beispiel 5.4 (nur) bei einer

”bosen“ Eingabereihenfolge (in der namlich erst die kleinen Tasks verteilt wurden)ein schlechtes Ergebnis.

Positiv formuliert ist List Scheduling per se ein Online-Algorithmus.

Im Folenden versuchen wir, die Eingabereihenfolge durch geeignetes Sortieren zuverbessern.

Schließlich mochten wir noch auf den Aspekt der Online-Algorithmen hinweisen,bei denen der Algorithmus nicht den Zugriff auf die gesamte Instanz zu jeder Zeithat, sondern ihn nur “bruchstuckweise” sieht und dann nach dem Bekanntwerdeneiner neuen Einzelheit auf unabanderliche Weise eine neue Teilentscheidung fallenmuss. Viele der hier besprochenen Algorithmen tragen diesen Wesenszug.

Neue Heuristische Idee: LPT (Largest Processing Time)

Sortiere eingangs die Tasks in absteigender Folge gemaß ihrer Laufzeit, d.h. es giltdann: l1 ≥ l2 ≥ . . . ≥ ln. Danach wird der LIST Scheduling Algorithmus auf diesortierte Liste angewendet. ; Algorithmus LPTLS

Satz 5.6 Ist x = (T = {t1, . . . tn}, p, l) eine Instanz von MSIM, so findet LPTLSeine Naherungslosung vom Wert mLPTLS(x), welche

mLPTLS(x)m∗(x)

≤(

43− 1

3p

)erfullt.

Beweis: Nach der Sortierung ist ln eine der kurzesten Tasklangen.Wir unterscheiden zwei Falle:

1. Fall: ln > m∗(x)/3. Dann konnen hochstens 2 Tasks auf eine Maschine gelegtwerden. LPTLS liefert hier sogar eine optimale Losung, wie man wie folgteinsieht.

a) Zunachst kommen p Tasks der Lange > m∗(x)/2. Da m∗(x) die optimaleLange ist, werden auch in jeder optimalen Losung nie zwei solcher Tasksauf einer Maschine abgearbeitet werden, und es stehen auf jeden Fallmehr Maschinen zur Verfugung als es Tasks der Lange > m∗/2 gibt(also p). LPTLS macht also ”nichts falsch“.

b) Dann kommen Tasks der Lange l, m∗(x)/2 ≥ l > m∗(x)/3. Die erstenmin(2(p − p), n − p) dieser Tasks werden von LPTLS auf die p − pMaschinen verteilt, die unter a) noch keine Arbeit bekamen. Wegenln > m∗(x)/3 sind diese p Maschinen somit soweit ausgefullt, dass siekeine weiteren Tasks mehr aufnehmen konnen. Wenn n− p = min(2(p−p), n − p), so ist die Zuweisung optimal. Es sei nun n > 2p − p. Zwar


konnten auch andere Maschinenzuweisungen zu optimalen Losungenfuhren, aber dann ware eine Losung, die durch ”Tausch“ von einem der2p− p betrachteten Tasks, die einer der ersten belasteten p Maschinenzugeordnet wurde, mit einer der n − 2p − p ”letzten“ Tasks, die dannevtl. einer der p− p anderen Maschinen zugeordnet worden ware, immernoch optimal; sollten alle p− p nach Schritt a) verfugbaren Maschinennur einen Task bekommen haben, durch den betreffenden optimalenAlgorithmus, so ist die ”Umverteilbarkeit“ ebenso klar. Mithin gibt eseine optimale Losung, die die ersten n − 2(p − p) Tasks genau so wieLPTLS verteilt.Sollten noch Tasks verbleiben, so mussen sie den p Maschinen zugewie-sen werden, denen LPTLS zuerst Arbeit unter a) zugewiesen hatte. Ein

”Tauschargument“ ahnlich dem obigen zeigt, dass die LPTLS-Losungoptimal ist.

Fur das abschließende Argument ubernehmen wir die Bezeichnungsweise vom Be-weis von Satz 5.3, insbesondere betreffend h und j.

2. Fall: ln ≤ m∗(x)/3.

Fall 2a: lj > m∗(x)/3 : Gilt lj > ln, so betrachte die ”abgeschnittene“ Instanzx′ = (T ′ = {t1, . . . , tj}, p, l′ = (l1, . . . , lj)), wobei wir die {t1, . . . , tn} alsabsteigend sortiert annehmen. Es gilt:

mLPTLS(x)m∗(x)

=mLPTLS(x′)

m∗(x)≤ mLPTLS(x′)

m∗(x′)= 1

nach Fall 1, denn m∗(x) ≥ m∗(x′).

Fall 2b: lj ≤ m∗(x)/3. Das Argument vom Beweis von Satz 5.3 zeigt:

mLPTLS(x) ≤ W

p+

(p− 1)p

· lj ≤ m∗(x) +p− 1

p· 13m∗(x)

≤(

3p + p− 13p

)m∗(x)

≤(

43− 1

3p

)m∗(x) 2

Uber Scheduling gibt es eigene Bucher wie:M. Pinedo: Scheduling: Theory, Algorithms and System, Prentice-Hall, 1995.P. Brucker: Scheduling Algorithms: 2nd. ed. Springer, 1998.Siehe auch Kap. 1 im Buch von Hochbaum!

5.2 Bin Packing

Beispiel 5.7 Auf fullen von Behaltern gleicher Kapazitat (Minimum Bin PackingMBP)


I : I = {a1, . . . , an}, ai ∈ (0, 1] ∩Q, 1 ≤ i ≤ nS : Partition P = {B1, . . . , Bk} von I mit ∀1 ≤ j ≤ k :

∑ai∈Bj

ai ≤ 1m : k = |P |opt : min.

Einfachste Heuristik: NextFit.I wird in der vorgegebenen Reihenfolge abgearbeitet. a1 wird in B1 platziert. Ist imVerlauf des Algorithmus Bj der zuletzt benutzte Behalter und wird ai betrachtet,so wird ai an Bj zugewiesen, falls es noch passt, und widrigenfalls an Bj+1.

Satz 5.8 Ist I = {a1, . . . , an} eine Instanz von MBP, so findet NextFit eine Losungvom Wert mNF (I) mit mNF (I)/m∗(I) ≤ 2.

Beweis: Sei A =∑n

i=1 ai. Da fur je zwei aufeinanderfolgende Behalter Bj , Bj+1

nach Ablauf von NextFit gilt, dass die Summe der Großen a(Bj) und a(Bj+1) dersich in Bj und Bj+1 befindenden Gegenstande großer als Eins ist (sonst waren sieja alle in Bj gelandet), gilt (mit k = mNF (I)):

2A = a(B1) +k−1∑l=1

(a(Bl) + a(Bl+1)) + a(Bk) > a(B1) + a(Bk) + k − 1

; 2A > k − 1 = mNF (I)− 1

Andererseits ist m∗(I) ≥ dAe. (Einheitsvolumen der Behalter!)

; mNF (I) < 2m∗(I) + 1.

Da die Werte ganzzahlig sind, folgt mNF (I) ≤ 2m∗(I). 2

Bemerkung 5.9 Die Schranke lasst sich verbessern, wenn bekannt ist, dass dieGegenstande eine Maximalgroße von α ≤ 1

2 haben; dann gilt:

mNF (I)/m∗(I) ≤ 11− α

.

Bemerkung 5.10 Die fur NextFit angegebene Schranke ist asymptotisch nichtverbesserbar.Betrachte dazu I = {a1, . . . , a4n} mit

ai ={

12 , i ungerade12n , i gerade

Offenbar istmNF (I) = 2n

undm∗(I) = n + 1.


NextFit ist in doppeltem Sinne ein Online-Algorithmus (und lasst sich daher auchin Linearzeit mit konstantem Speicher implementieren):

1. Die Gegenstande werden ”der Reihe nach“ (so wie sie in der Eingabe stehen)betrachtet. Insbesondere werden sie nicht sortiert.

2. Ein Behalter, in den einmal ein Gegenstand nicht hineingetan wurde, wirdnie wieder betrachtet. Er wird sozusagen ”geschlossen“.

Wenn man Punkt 2 fallenlasst, braucht man evtl. mehr Speicher, um sich allemoglichen ”geoffneten“ Behalter merken zu konnen. Der Algorithmus FirstFit offneterst dann einen neuen Behalter, wenn der betrachtete Gegenstand ai nicht in einender bereits geoffneten Behalter passt. Passt ai in einen der geoffneten Behalter, sotut FirstFit ihn in den ersten passenden (daher der Name).

Mitteilung 5.11 Ist I = {a1, . . . , an} eine Instanz von MBP, so findet FirstFiteine Losung vom Wert mFF (I) mit

mFF (I) ≤ d1, 7 ·m∗(I)e [siehe Kapitel 2 im Buch von Hochbaum]

Noch besser steht ”FirstFitDecreasing“ da; dieser Algorithmus lasst auch nochPunkt 1 fallen und sortiert zunachst die Eingabe, bevor der FirstFit-Algorithmusangewendet wird. In seiner Doktorarbeit hat D. S. Johnson 1973 auf uber 70 Seitenfolgendes bewiesen:

Mitteilung 5.12 Ist I = {a1, . . . an} eine Instanz von MBP, so findet FirstFitDe-creasing eine Losung vom Wert mFFD(I) mit

mFFD(I) ≤ 119

m∗(I) + 4

B. S. Baker hat 1985 im Journal of Algorithms 6: 49–70 einen kurzeren Beweis fur

mFFD ≤119

m∗(I) + 3

gegeben.Wir beschranken uns im folgenden darauf, eine schlechtere Schranke zu beweisen.

Satz 5.13 Ist I = {a1, . . . , an} eine Instanz von MBP, so findet FirstFitDecreasingeine Losung vom Wert mFFD(I) mit

mFFD(I) ≤ 1, 5 ·m∗(I) + 1.


Beweis: Betrachte I = A ∪B ∪ C ∪D mit

A =

{ai | ai >

23

},

B =

{ai | 2

3≥ ai >

12

},

C =

{ai | 1

2≥ ai >

13

},

D =

{ai | 1

3≥ ai

}.

Gibt es einen Behalter, der ausschließlich mit Gegenstanden aus D gefullt wurde, sosind alle Behalter —mit moglicher Ausnahme des zuletzt geoffneten— zu wenigstens2/3 gefullt, woraus die Behauptung hier folgt, denn

m∗(I) ≥⌈∑

ai

⌉≥ 2

3mFFD(I).

Gibt es keinen Behalter, der nur Gegenstande aus D enthalt, so gilt:

mFFD(I) = mFFD(I \D),

da alle Behalter auch Gegenstande aus I \D enthalten und die Vorsortierung be-wirkt, dass Gegenstande aus I \ D bei der Instanz I nicht anders als bei der In-stanz I \ D behandelt werden. Wir zeigen nun mFFD(I \ D) = m∗(I \ D), wor-aus mFFD(I) ≤ m∗(I) folgt. Jedenfalls ist m(I \ (D ∪ A)) + |A| = m(I \ D) furm ∈ {m∗,mFFD}. Gegenstande von B und C werden nun gunstigenfalls ”paarwei-se“ gegliedert, und zwar ”kleine“ aus C und mit ”großen“ aus B. Das genau machtmFDD, woraus m∗(I \ (D ∪A)) = mFFD(I \ (D ∪A)) folgt. 2

Bemerkung 5.14 Um die asymptotische Scharfe der Mitteilung einzusehen, be-trachte fur n > 0 (n durch 6 teilbar), die Instanz I5n, die folgende Gegenstandeenthalt.

n Gegenstande der Große 1/2 + ε (Typ 1)n Gegenstande der Große 1/4 + 2ε (Typ 2)n Gegenstande der Große 1/4 + ε (Typ 3)

2n Gegenstande der Große 1/4− 2ε (Typ 4)

Bestmoglicherweise braucht man 32n Behalter:

n Behalter sind mit je einem Gegenstand vom Typ 1, 3 und 4 gefullt,n2 Behalter sind mit je zwei Gegenstanden vom Typ 2 und zweien vom Typ 4 gefullt.Dagegen wurde FFD wie folgt fullen:


n Behalter mit je einem Gegenstand vom Typ 1 und 2,n3 Behalter mit je drei Gegenstanden vom Typ 3,n2 Behalter mit je vier Gegenstanden vom Typ 4.

Also gilt:mFFD(I5n)

m∗(I5n)=

116 n32n

=119

.

Aufgrund der Paxisrelevanz von MBP (z.B. Containerbeladung, Zuschnittproblemeaus Standardstucken) und seiner (oft mehrdimensionaler) Varianten ist die Litera-tur zu MBP immens, vgl. auch das 2. Kapitel im Buch von Hochbaum.

5.3 Graphenfarben

ist ein Problem, das nicht sofort als Partitionsproblem ”vorliegt“.

I : Graph G = (V,E)S : {f : V → N | f ”Farbung“, d.h. ∀{v1, v2} ∈ E : f(v1) 6= f(v2)}m : |f(V )|opt : min.

Graphenfarben ist insofern ein Partitionierungsproblem, als dass V in ”gleichfarbigeMengen“ unterteilt werden soll.Die entsprechende Partitionierungsheuristik wurde also einen neuen ”Knoten“ vi

zu einer ”alten“ Farbmenge Vc (Partitionsmenge) hinzufugen, sofern kein Nachbarvon vi bereits in Vc liegt. Widrigenfalls wurde eine neue Farbe gewahlt.

Satz 5.15 Betrachte die Knotenmenge des Eingabegraphen G = (V,E) als geord-net: (v1, . . . , vn). (Dies ist auch die Reihenfolge, in der die Partitionsheuristik ar-beitet.)Es sei Gi = G({v1, . . . , vi}); di(v) bezeichne den Grad von v in Gi.Die Partitionsheuristik benotigt dann hochstens

max1≤i≤n

min(dn(vi), i− 1) + 1

viele Farben zum Farben von G.

Beweis: Es sei ki die Farbanzahl, die der Algorithmus zum Farben von Gi benotigt.Wird keine neue Farbe eingefuhrt, so gilt in dieser Notation ki = ki−1.Sonst gilt: ki = ki−1 + 1 und di(vi) ≥ ki−1 (sonst brauchte man keine neue Farbe).Wir wollen zeigen:

kj ≤ max1≤i≤j

(di(vi)) + 1

j = 0, 1 :√

j → j + 1 : Ist kj+1 = kj , so ist die Behauptung per Induktionsannahmewahr.Ist kj+1 = kj + 1, so gilt:kj+1 = kj + 1 ≤ dj+1(vj+1) + 1 ≤ max

1≤i≤j+1di(vi) + 1.


Wegen di(vi) ≤ dn(vi) und di(vi) ≤ i− 1 folgt die Behauptung. 2

Folgerung 5.16 Ist ∆ der Maximalgrad von G, so liefert die Partitionsheuristikeine Farbung von G mit hochstens ∆ + 1 vielen Farben bei beliebiger Anordnungder Knoten.

Um den Ausdruckmax

1≤i≤nmin(dn(vi), i− 1)

moglichst klein zu bekommen, erscheint das Anordnen der Knoten des Graphennach absteigendem Grad sinnvoll.Leider gestattet ein solcher Algorithmus im Allgemeinen keine vernunftigen Gute-abschatzungen (und dies ist kein Zufall, wie wir noch spater sehen werden).

Betrachte namlich G = (V,E) mit

V = {x1, . . . , xn, y1, . . . , yn}, E = {{xi, yj} | i 6= j}

sowie die Knotenanordnung(x1, y1, x2, y2, . . .)

Obwohl der Graph zweifarbbar ist (in ”x“- und ”y“-Farben) benotigt (auch dievorsortierte) Partitionsheuristik hier n Farben (gemaß den Knotenindizes).

6 LOKALE SUCHE 56

6 Lokale Suche

Die lokale Suche ist ein beliebte Heuristik, die nach folgendem Schema verfahrt:

1. Initialisiere y mit (irgendeiner) zulassigen Losung

2. Solange es in der ”Nachbarschaft“ von y eine Losung z gibt, die besser als yist, setze y := z.

3. Liefere (lokales Optimum) y zuruck.

Um fur ein spezielles Problem einen auf lokaler Suche fußenden Algorithmus zuentwerfen, benotigen wir daher zweierlei:

a) ein Verfahren, um den in Schritt 1 erforderlichen Startwert (d.h., um irgendeinezulassige Losung) zu finden sowie

b) einen geeigneten ”Nachbarschaftsbegriff“ auf dem Raum der zulassigen Losungen.

Weiterhin muss folgendes gewahrleistet sein, damit ”lokale Suche“ als Naherungs-algorithmusstrategie taugt:

(i) Schritt 1 (siehe a) ) geht polynomiell.

(ii) Die gemaß b) definierte Nachbarschaft lasst sich in Polynomzeit auf bessereLosungen hin untersuchen (Schritt 2).

(iii) Der Gesamtalgorithmus findet nach polynomiell vielen Schritten ein lokalesOptimum.

6.1 Großtmoglicher (Kanten-)Schnitt (Maximum Cut MC)

I : Graph G = (V,E)S : {{V1, V2} | V1, V2 ⊆ V, V1 ∩ V2 = ∅, V1 ∪ V2 = V }m : |C(V2, V2)|, mit C(V1, V2) = {e ∈ E | e ∩ V1 6= ∅ ∧ e ∩ V2 6= ∅}opt : maxWir wollen lokale Suche fur MC anwenden.

zu a): Nimm V1 = ∅, V2 = V (ist also trivial)

zu b) N ({V1, V2}) = {{U1, U2} ∈ S | ∃v ∈ V : U1 4 V1 = U2 4 V2 = {v}}(Hamming-Nachbarschaft)4 bezeichnet die symmetrische Differenz von Mengen, d.h.:A4B = A \B ∪B \A.

Satz 6.1 Ist G = (V,E) eine Instanz von MC und ist {V1, V2} ein lokales Optimumbzgl. der obigen Nachbarschaft N ({V1, V2}) mit dem Wert mN (G), dann gilt:

m∗(G)/mN (G) ≤ 2.

Daher liefert die lokale Suche eine polynomielle 2-Approximation.

6 LOKALE SUCHE 57

Beweis: Wir betrachten die Eingabe G = (V,E). “Lokale Suche” ist sicher polyno-mial, da mit der Suche nur weitergemacht wird, wenn der Kantenschnitt vergroßertwerden kann und daher hochstens |E| viele lokale Suchen durchgefuhrt werden.Jeder lokale Suchschritt ist sicher auch in Polynomzeit durchzufuhren.

Ist m := |E|, so gilt sicher m∗(G) ≤ m. Wir zeigen jetzt:

mN (G) ≥ m

2.

Ist mi := |E(G(Vi))| , i = 1, 2, so gilt:

m = m1 + m2 + mN (G) (∗)

Ist Vi,u = {v ∈ Vi | {u, v} ∈ E}, i = 1, 2, und ist mi,u := |Vi,u|, so gilt wegen derlokalen Optimalitat von {V1, V2}:

m1,u ≤ m2,u, falls u ∈ V1 (sonst {V1 \ {u}, V2 ∪ {u}} ”besser“)

m1,u ≥ m2,u, falls u ∈ V2 (sonst {V1 ∪ {u}, V2 \ {u}} ”besser“)

Daraus folgt: ∑u∈V1

(m1,u −m2,u) = 2[!] ·m1 −mN (G) ≤ 0

sowie ∑u∈V2

(m2,u −m1,u) = 2 ·m2 −mN (G) ≤ 0;

zusammen; m1 + m2 −mN (G) ≤ 0

(∗); m ≤ 2mN (G) 2

Im Allgemeinen ist lokale Suche eine beliebte Heuristik, die Schwierigkeit bestehtdarin, Gutegarantien nachzuweisen. Auch wenn es solche Garantien nicht gebensollte, sind lokale Suchalgorithmen haufig in der Praxis wertvoll, z.B. bei TSP.

7 LINEARES PROGRAMMIEREN 58

7 Lineares Programmieren

7.1 Allgemeines

Lineare Optimierungsaufgaben wurden erstmal sustematisch in den vierziger Jahrendes 20. Jahrhunderts im Zusammenhang der ”Mangelverwaltung“ der Nachkriegs-zeit untersucht. Aus dieser Zeit stammt auch der Terminus ”Lineares Programmie-ren “ (LP); heute wurden wir eher von ”linearem Optimieren“ sprechen, denn mitProgrammieren im Sinne von Informatik hat LP (zunachst) nichts zu tun.Eine LP-Aufgabe ist gegeben durch n reellwertige Variablen, zusammen gefasstals Vektor ~x = (x1, . . . , xn), eine Zielfunktion (d.h. eine Linearkombination aus denVariablen), die es zu minimieren oder zu maximieren gilt unter der Einschrankung,dass die Losung m gegebenen linearen Ungleichungen genugt.Wie wir noch zeigen werden, lasst sich jedes lineare Programm wie folgt formulieren:

Ggb: ~c ∈ Rn,~b ∈ Rm, A ∈ Rm×n

minimiere ~c T · ~xunter den Bedingungen A~x ≥ ~b,

~x ≥ ~0.

(∗)

Das immer noch beliebteste Verfahren zur Losung von LPs stammt von Dantzig,das so genannte Simplexverfahren. Dieses Verfahren durchlauft die Ecken desdurch A~x ≥ ~b angegebenen Polyeders; nur dort konnen optimale Losungen liegen.Dies fuhrt allerdings dazu, dass es LP-Aufgaben gibt, bei denen das Simplexver-fahren Exponentialzeit benotigt. Theoretisch (!) besser ist daher die von Khachianentwickelte Ellipsoidmethode, die stets in Polynomzeit arbeitet.Wir werden beide Verfahren hier nicht weiter erlautern, sondern das Wissen um sieals Black Box im Folgenden beutzen. Es gibt auch spezielle Softwarepakete fur LP,die man in den folgenden Programmen einsetzen konnte.

7.2 Aquivalente Formulierungen

Es gibt andere Formulierungen von LP-Aufgaben, die sich leicht in die Form (∗)bringen lassen.Beispiele hierfur seien im Folgenden kurz erlautert:

Ggb: ~c ∈ Rn,~b ∈ Rm,~b′ ∈ Rl, A ∈ Rm×n, A′ ∈ Rl×n, r ≤ nminimiere ~c T · ~xunter den Bedingungen A~x ≥ ~b,

A′~x = ~b′

x1 ≥ 0, . . . , xr ≥ 0

Uberfuhrung in die Form (∗):


• Jede Gleichheitsbedingung ~a′ · ~x = b′i kann durch zwei lineare Ungleichungenausgedruckt werden: ~a′ · ~x ≥ b′i und −~a′ · ~x ≥ −b′i.

• Jede Variable xj ohne Vorzeichenbeschrankung wird durch zwei Variablenx+

j , x−j ersetzt mit x+j ≥ 0, x−j ≥ 0;

jedes Vorkommen von xj im ursprunglichen Linearen Programm wird durch(x+

j − x−j ) ersetzt.

Man kann die linearen Ungleichungsbedingungen in (∗) auch durch lineare Glei-chungsbedingungen ersetzten. Dies fuhrt auf das folgende Problem:


minimiere ~c T · ~xunter A~x = ~b,

und ~x ≥ ~0

Dazu ist jede Ungleichung ~a · ~x ≥ bi durch zwei Bedingungen ~a · ~x − si = bi undsi ≥ 0 zu ersetzen; die neu eingefuhrte Variable si heißt auch Schlupfvariable.Durch Ubergang von ~c auf (−~c ), von ~b auf (−~b) und von A auf (−A) lasst sich auchdie folgende Maximierungsaufgabe leicht in die Form (∗) bringen:


maximiere ~c T · ~x ; minimiere (−~c )T · ~xunter A · ~x ≤ ~b,

~x ≥ ~0unter (−A) · ~x ≥ ~−b,

~x ≥ ~0

7.3 Duale Programme

Zu jeder (zur Unterscheidung auch primal genannten) gegebenen LP-Minimie-rungsaufgabe lasst sich das so genannte duale Maximierungsprogramm wie folgtangeben:

Primal DualBedingung i:

∑nj=1 aijxj ≥ bi Variable yi: yi ≥ 0

Variable xj : xj ≥ 0 Bedingung∑m

i=1 aijyi ≤ cj

minimiere ~c T ~x maximiere ~b T ~y

Dabei gehen wir von einem primalen Programm der Form (∗) aus mit A = (aij |1 ≤ i ≤ m, 1 ≤ j ≤ n), ~x = (xj | 1 ≤ j ≤ n), ~b = (bj | 1 ≤ j ≤ m) und~c = (ci | 1 ≤ i ≤ n).

Der Dualitatssatz besagt, dass fur (losbare) Lineare Programme gilt:

min{~c T · ~x | ~x ≥ 0, A~x ≥ ~b

}= max

{~b T · ~y | ~y ≥ 0, ~y T A ≤ ~c

}.


7.4 Ganzahliges Programmieren und Relaxation

Aus (∗) (oder einer der besprochenen Umformulierungen) entsteht ein ganzahligelineares Programm, indem zusatzlich gefordert wird, dass zulassige Losungen stetsnur ganzzahlig sind oder gar nur bestimmte ganze Zahlen als Losung akzeptiertwerden. Wahrend LP (wie gesagt) in Polynomzeit losbar ist, ist ILP (integer LP)ein NP-hartes Problem. Es ist fur uns jedoch von Interesse, da

• viele Optimierungsaufgaben sich als ILP formulieren lassen und

• die Vernachlassigung (”Relaxation“) der Ganzzahligkeitsbedingungen zu ei-nem LP fuhrt, dessen Losung eine Schranke fur das ursprungliche ILP bietet;die weiter gehende Hoffnung ist, dass man durch einfache Operationen wieRunden aus der LP-Losung eine moglichst gute ILP-Losung generieren kann.

Ein konkretes Beispiel: das gewichtete Knotenuberdeckungsproblem (vgl. Ab-schnitt 2.2) lasst sich wie folgt als ILP ausdrucken:

minimiere∑

vi∈V cixi

unter xi + xj ≥ 1 fur {vi, vj} ∈ Exi ∈ {0, 1} fur vi ∈ V

Ausgegangen wird dabei von einem Graphen G = (V,E), V = {v1, . . . , vn} mitKnotenkosten ci(ci ≥ 0) fur vi. Die Variable xi ”entspricht“ dem Knoten vi unddie Bedingung xi + xj ≥ 1 ”entspricht“ der Kante {vi, vj}.

Daher ist eine Knotenmenge C ⊆ V , gegeben durch C = {vi | xi = 1}, genau danneine Knotenuberdeckung, wenn fur alle Kanten {vi, vj} die Ungleichung xi +xj ≥ 1gilt.Eine mogliche Relaxation ist die folgende:

minimiere∑

vi∈V cixi

unter xi + xj ≥ 1 fur {vi, vj} ∈ Eund xi ≥ 0, i = 1, . . . , n

Betrachte nun folgendes Programm:

RoundVC(G = (V,E),~c)

1. Bestimme die ILP-Formulierung des VC-Problems.

2. Bestimme die zugehorige LP-Formulierung durch Relaxation.

3. Es sei ~x∗G = (x∗1, . . . , x∗n) eine optimale Losung fur die Relaxation.

4. Liefere {vi | x∗i ≥ 0, 5} zuruck.

Die Knotenuberdeckung wird also durch Runden der LP-Losung gewonnen.

Satz 7.1 RoundVC findet eine zulassige Losung eines gewichteten Knotenuberdeckungsproblemsvom Wert mLP (G,~c ) mit

mLP (G,~c ) /m∗ (G,~c ) ≤ 2.


Beweis: Die von RoundVC gelieferte Losung {vi | x∗i ≥ 0, 5} ist eine Knotenuberdeckung.Ware namlich e = {vi1vi2} eine nicht abgedeckte Kante, so ware x∗i1 + x∗i2 < 1, imWiderspruch zur Annahme, ~x∗G sei Losung der Relaxations-LP-Aufgabe.Umgekehrt ist jede Losung der ILP-Aufgabe auch eine Losung der LP-Aufgabe,sodass insbesondere fur die optimalen Losungen gilt:

m∗ (G,~c ) ≥ m∗LP (G,~c ) =

∑vi∈V

cix∗i .

Weiter ist:

mLP (G,~c ) =∑

x∗i≥0,5 1≤i≤n

ci

≤ 2 ·∑

1≤i≤n

cix∗i

= 2 · ~c T · ~x∗G= 2 ·m∗

LP (G,~c )≤ 2 ·m∗ (G,~c ) 2

7.5 Primal-Duale Algorithmen fur ILP

Nachteil von RoundVC ist, dass lineare Programme mit vielen Ungleichungsbedin-gungen zu losen sind. Daher hat der entsprechende LP-Algorithmus eine (zu) großeLaufzeit. Die Idee ist nun, (irgendwelche) zulassigen Losungen fur das zugehorigeduale LP zu benutzen, um Schranken fur das eigentlich zu losende ILP zu gewinnen.Genauer sieht diese Uberlegung wie folgt aus:

Betrachte ein (Minimierungs-)ILP, die zugehorige Relaxation LP sowie dessen (Maxi-mierungs-)Dual-DLP mit optimalen Werten x∗ILP , x∗LP und x∗DLP . Aus dem Dua-litatssatz ergibt sich fur eine Verteilung der Werte von Losungen auf der Zahlenge-raden:

X LP*

=X*DLP

Zulässige Lsg. von DLP Zulässige Lsg. von ILP

X*ILP

Tatsachlich wird bei den Primal-Dual-Naherungsalgorithmen fur ILPs vermieden,explizit die optimale Schranke x∗LP = x∗DLP zu berechnen; es werden statt dessensukzessive bessere zulassige Losungen des DLPs berechnet.

Wir geben Konkret ein Beispiel:

PDVC (G,~c)


1. Bestimme die ILP-Formulierung des VC-Problems.

2. Bestimme die zugehorige LP-Formulierung durch Relaxation.

3. Bestimme die zugehorige DLP-Formulierung.

Bemerkung: DLPV C lautet:maximiere

∑{vi,vj}∈E y{i,j}

unter∑

j:{vi,vj}∈E y{i,j} ≤ ci fur jedes vi ∈ V

y{i,j} ≥ 0 fur alle {vi, vj} ∈ E

4. Setze jede duale Variable y{i,j} auf Null.[Dies ist eine zulassige Losung des DLP.]

5. V ′ := ∅; [V ′ enthalt die Knoten der Uberdeckungsapproximation.]

6. Solange V ′ keine Knotenuberdeckung ist, tue:

6a. Wahle Kante e = {vi, vj} mit e ∩ V ′ = ∅.6b.

ε := min

ci −∑

k:{vi,vk}∈E

y{i,k}, cj −∑

k:{vj ,vk}∈E

y{j,k}

6c.

y{i,j} := y{i,j} + ε

6d. Wenn ∑k={vi,vk}∈E

yi,k = ci

dann V ′ := V ′ ∪ {vi}sonst V ′ := V ′ ∪ {vj}

7. Gib V ′ aus.

Satz 7.2 PDVC findet eine zulassige Losung des gewichteten Knotenuberdeckungs-problems vom Wert mPD (G,~c) mit

mPD (G,~c)m∗ (G,~c)

≤ 2.

Beweis: Die Schleife in Schritt 6 wird erst verlassen, wenn in V ′ eine zulassigeLosung ”aufgesammelt“ wurde.Schritt 6d gewahrleistet fur die von PDVC gelieferte Uberdeckung V ′:

∀vi ∈ V ′ :∑

j:{vi,vj}∈E

y{i,j} = ci


Also ist:

mPD (G,~c) =∑

vi∈V ′

ci

=∑

vi∈V ′

∑j:{vi,vj}∈E

y{i,j}

≤∑vi∈V

∑j:{vi,vj}∈E

y{i,j}

= 2 ·∑

{vi,vj}∈E

y{i,j}

≤ 2 ·m∗ (G,~c) ,

denn∑

{vi,vj}∈E y{i,j} ist der Wert einer zulassigen Losung des DLP. 2

Bemerkung 7.3 Der soeben vorgestellte Algorithmus PDVC ist tatsachlich derschon in Abschnitt 2.4 behandelte von Bar-Yehuda und Even. Um dies einzusehen,setze man anfangs in PDVC w(vi) := ci als Gewichtsreduzierung und als Schritt

”6e“ fuge man w(vi) := w(vi) − ε und w(vj) := w(vj) − ε ein. Dann gilt offenbarstets:

w(vi) = ci −∑

k:{vi,vk}∈E

y{i,k}.

In termini des Kapitels 2 ist ε daher der Nicht-Null-Wert der Gewichtsreduktions-funktion δ{vi,vj}.

Dieser Zusammenhang lasst sich noch allgemeiner darstellen, siehe auch:R. Bar-Yehuda, D. Rawitz : On the equivalence between the primal-dual schemeand the local-ratio technique. Seiten 24–35 IN: M. Goemanns u.a.: Approximation,Randomization and Combinatorical Optimization, LNCS 2129, Springer, 2001.

8 DYNAMISCHES PROGRAMMIEREN 64

8 Dynamisches Programmieren

Dynamisches Programmieren ist im Grunde genommen eine Technik, wie aus Op-tima, die fur Teilprobleme des ursprunglichen ermittelt wurden, das Optimum furdas Grundproblem berechnet werden kann. Dabei werden Mehrfachberechnungendurch Buchfuhrung (in einer Tabelle) vermieden.9 Die Tabelle wird dabei sukzessi-ve von kleinen zu immer großeren Problemen hin aufgebaut. Wir werden in diesemKapitel —allgemeiner gesprochen— sehen, wie man Losungsstrategien, die stets dasOptimum liefern, aber (vermutlich notgedrungen) eine superpolynomielle Laufzeithaben, dazu benutzen kann, Naherungsalgorithmen zu entwerfen.Betrachten wir diese Vorgehensweise fur das schon bekannte Rucksackproblem.

8.1 Ein exakter Algorithmus fur das Rucksackproblem

Gegeben sind also: eine Rucksackkapazitat b ∈ N, Gegenstande {x1, . . . , xn} mitzugehoriger Großenangabe ai ∈ N und Profitangabe pi ∈ N.

Wir wollen davon ausgehen,

• dass alle Gegenstande der Instanz einzeln in den leeren Rucksack passen; d.h.formal, dass ∀i : ai ≤ b, und

• dass nicht alle Gegenstande der Instanz zusammen in den leeren Rucksackpassen; d.h. formal, dass

∑ni=1 ai > b; sonst ware die optimale Losung ja

trivial zu bekommen.

Fur das dynamische Programmieren betrachten wir fur jedes 1 ≤ k ≤ n und jedes0 ≤ p ≤

∑ni=1 pi das Problem, eine Teilmenge von {x1, . . . , xn} zu finden mit Ge-

samtprofit p und Gesamtgroße hochstens b. Es bezeichnen M∗(k, p) ⊆ {x1, . . . , xk}eine optimale Losung dieses Problems und S∗(k, p) die entsprechende Gesamtgroße.Als Sonderfall setzen wir S∗(k, p) := 1 +

∑ni=1 ai, falls M∗(k, p) undefiniert ist.

Damit gilt

M∗(1, p) =

∅, p = 0{x1}, p = p1

undefiniert, sonst

Fur k ≥ 2 gilt der folgende (rekursive) Zusammenhang:

M∗(k, p) =

M∗(k − 1, p− pk) ∪ {xk} falls gilt: (i) pk ≤ p,(ii) M∗(k − 1, p− pk) ist definiert,(iii) S∗(k − 1, p)

≥ S∗(k − 1, p− pk) + ak

(iv) S∗(k − 1, p− pk) + ak ≤ bM∗(k − 1, p) sonst

In Worten heißt dies: Die beste Teilmenge von {x1, . . . xk} mit Profit p ist entwederdie beste Teilmenge von {x1, . . . , xk−1} mit Profit p (d.h., xk ist in jener Teilmenge

9bekanntes Beispiel aus Grundvorlesung: CYK-Algorithmus


nicht enthalten) oder es ist die beste Teilmenge von {x1, . . . , xk−1} mit Profit p−pk

(plus Gegenstand xk).

Dynamisches Programmieren bedeutet nun, die Werte von M∗ und S∗ fur aufstei-gende Argumente der Reihe nach zu berechnen.

Konkret sieht der Algorithmus wie folgt aus:

KnapsackDynProg (X = {x1, . . . , xn}, {p1, . . . , pn}, {a1, . . . , an}, b)

1. Fur p := 0 bis∑n

i=1 pi tue

1a. Setze M∗(1, p) := undefiniert

1b. Setze S∗(1, p) := 1 +∑n

i=1 ai

2a. M∗(1, 0) := ∅;S∗(1, 0) := 0;

2b. M∗(1, p1) := {x1};S∗(1, p1) := a1;

3. Fur k := 2 bis n tue:Fur p := 0 bis

∑ni=1 pi tue:

3a. Falls pk ≤ p und M∗(k − 1, p− pk) ist definiertund S∗(k − 1, p− pk) + ak ≤ min{b, S∗(k − 1, p)}dann

3a1. Setze M∗(k, p) := M∗(k − 1, p− pk) ∪ {xk}3a2. Setze S∗(k, p) := S∗(k − 1, p− pk) + ak

3b. sonst

3b1. Setze M∗(k, p) := M∗(k − 1, p);3b2. Setze S∗(k, p) := S∗(k − 1, p)

4. Sei p∗ das maximale p, fur das M∗(n, p) definiert ist.(Beachte: M∗(n, 0) = ∅ ist stets definiert!)

5. Liefere M∗(n, p∗).

Satz 8.1 KnapsackDynProg findet stets eine optimale Losung, und zwar in Zeit

O(n ·n∑

i=1

pi).

Hinweis: Diese Laufzeit ist nicht polynomiell, da die pi als binar codiert angenom-men werden. Solche so genannten pseudopolynomialen Algorithmen untersuchenwir naher in Kap. 12.


8.2 Ein Naherungsverfahren fur das Rucksackproblem

KnapsackFPTAS (X = {x1, . . . , xn}, {p1, . . . , pn}, {a1, . . . an}, b, r)(r ∈ Q, r > 1 ist der angestrebte Approximations-Leistungsfaktor)

1. pmax := max{pi | 1 ≤ i ≤ n};

2. t :=⌊log2(

r−1r ·

pmax

n )⌋;

3. x′ := Instanz mit Profiten p′i := bpi/2tc ;

4. Liefere KnapsackDynProg(x′).

Satz 8.2 Gegeben seien eine Instanz x von MaximumKnapsack (mit n Gegenstanden)und r > 1, r ∈ Q. KnapsackFPTAS(x) liefert eine Losung in Zeit O(r ·n3/(r− 1)),deren Maß mAS(x, r) der Ungleichung m∗(x)/mAS(x, r) ≤ r genugt.

Beweis: Es bezeichne Y (x, r) die von KnapsackFPTAS gelieferte Losung und Y ∗(x)eine optimale Losung von Instanz x (mit Maß m∗(x)).

Es gilt:

mAS(x, r) =∑

xj∈Y (x,r) pj ≥∑

xj∈Y (x,r) 2t · bpj/2tc

(nach Definition der b·c-Funktion)≥

∑xj∈Y ∗(x) 2t · bpj/2tc

(denn∑

xj∈Y (x,r) bpj/2tc ist deroptimale Wert des ”skalierten Problems“)

≥∑

xj∈Y ∗(x) (pj − 2t)(nach Definition der b·c-Funktion)

=(∑

xj∈Y ∗(x) pj

)− 2t · |Y ∗(x)|

= m∗(x)− 2t · |Y ∗(x)|

; m∗(x)−mAS(x, r) ≤ 2t · |Y ∗(x)| ≤ 2t · nOffenbar gilt ferner: n · pmax ≥ m∗(x) ≥ pmax

};

;m∗(x)−mAS(x, r)

m∗(x)≤ n · 2t

pmax

⇒ m∗(x) ≤ pmaxpmax−n·2t mAS(x, r)

≤ pmax

pmax−n· r−1r · pmax

n

mAS(x, r)

= r ·mAS(x, r)

Laufzeitabschatzung:

O (n ·∑n

i=1 p′i) ≤ O(n ·∑n

i=1pi

2t

)≤ O

(n2 pmax

2t

)≤ O

(n2 pmax

r−1r

pmaxn

)= O

(n3 · r

r−1

)2


Bemerkung 8.3 Naheres zu Approximationsschemata und vollen Approximati-onsschemata s. Kap. 12.

9 WEITERE STRATEGIEN 68

9 Weitere Strategien - Was tun bei konkreten Pro-blemen?

In den vorigen Kapiteln haben wir verschiedene Strategien kennen gelernt um Ap-proximationsalgorithmen zu entwerfen. Leider ist diese Liste nicht vollstandig, dennAlgorithmenentwurf ist i.A. ein sehr kreativer Prozess. Dabei ist es manchmal hilf-reich, sich an einen altbekannten Algrithmus zu erinnern.Betrachten wir das folgende graphentheoretische Problem, welches wichtig ist umdie Zuverlassigkeit von Netzmodellen zu erhohen.

Billigste Erweiterung zu starkem Zusammenhang

I : G = (V,A) gerichteter, vollstandiger Graph mit Kantenkostenfunktionc : A→ N, eine vorliegende Kantenmenge A0

S : {A1 ⊆ A \A0 | (V,A0 ∪A1) ist stark zusammenhangend}Ein gerichteter Graph heißt stark zusammenhangend, wenn eszwischen je zwei Knoten einen (gerichteten) Pfad gibt.

m : c(A1)opt : min.

Hinweis: Das Problem ist NP-vollstandig.

Die Idee, die man hierfur haben konnte, ist folgende:

Bekanntermaßen lasst sich ein minimaler Spannbaum in Polynomzeit finden. Kannman nun erzwingen, dass (durch geeignete Modifikation der Kantengewichte) zweiBaume T1 und T2 (aufgefasst als Kantenmenge) mit gleicher Wurzel r, aber un-terschiedlicher Pfeilrichtung gefunden werden, so gibt es in dem Graphen, der nuraus den so gewichteten Baumkanten besteht, zwischen je zwei Knoten x und yjedenfalls einen Pfad von x nach y, der uber r fuhrt. Auf diese Weise ließe sicheine 2-Approximation gewinnen, denn eine optimale Erweiterung C∗ musste (ingewissem Sinne) auch die Baume T1 und T2 enthalten.

Konkretisieren wir diese Idee:

STC(G = (V,A), c, A0)

1. Definiere neue Abstandsfunktion d1 wie folgt:

d1(u, v) ={

0, falls (v, u) ∈ A0

c((v, u)), falls (v, u) /∈ A0

2. Finde minimalen Spannbaum T1 (aufgefasst als Kantenmenge).Sei r die Wurzel von T1.Setze A1 = {(u, v) | (v, u) ∈ T1}.


3. Definiere Abstandsfunktion d2 wie folgt:

d2(u, v) =

0, (u, v) ∈ A0 ∪A1

∞, v = rc((u, v)), sonst

4. Finde minimalen Spannbaum T2 (mit Abstandsfunktion d2).

5. Liefere (A1 ∪ T2) \A0.

Satz 9.1 STC ist eine 2-Approximation fur das Problem, eine billigste Erweiterungzu starkem Zusammenhang zu finden.

Beweis: Durch die Definition von d2 wird erzwungen, dass r (ebenfalls) die Wurzelvon T2 ist, sodass tatsachlich eine Erweiterung geliefert wird, die starken Zusam-menhang garantiert. In Schritt 2 wird eine Kantenmenge T1 gefunden, sodass jederKnoten mit der Wurzel r durch einen Pfad verbunden ist. In einer optimalen Er-weiterung C∗ gibt es naturlich auch einen solchen Pfad.Da T1 minimaler Spannbaum ist, gilt c(T1 \ A0) = d1(T1) ≤ d1(C∗) = c(C∗). Istnamlich T ′

1 ein minimaler Spannbaum in G(A0 ∪C∗) (bzgl. des Abstandmaßes d1),so ist sicher d1(T1) ≤ d1(T ′

1), da T1 auch andere, evtl, billigere Kanten benutzendarf. Da T ′

1 eine Kantenteilmenge von C∗ ist, gilt d1(T ′1) ≤ d1(C∗).

Entsprechend sieht man: c(T2 \ (A0 ∪ T1)) = d2(T2) ≤ d2(C∗) ≤ c(C∗). 2

Literatur:

• K. P. Eswaran and R. E. Tarjan: Augmentation problems. SIAM J. Compu-ting 5(1976), 653–665.

• G. N. Frederickson and J. Jaja: Approximation algorithms for several graphaugmentation problems. SIAM J. Computing 10(1981), 270–283.

• H. Nagamochi and T. Ibaraki: An approximation for finding the smallest2-edge connected subgraph containing a specified spanning tree. In: T. Asa-no u.a. (Herausgeber), Proc. COCOON’99, LNCS Band 1627, pp. 221–230.Springer, 1999.

Hinweis: Erweiterungsprobleme sind wichtig, wenn es darum geht, (bestehende)(Rechner-)Netzwerke ausfallsicherer zu machen. Daher wird in den genannten Re-ferenzen auch das Problem besprochen, einen gegebenenen zusammenhangendenungerichteten Graphen k-fach mit moglichst geringem Aufwand (insbesondere zwei-fach) zusammenhangend zu machen, um mehrere unabhangige ”Kommunikations-wege“ zwischen ”Rechenknoten“ zu gewahrleisten.


Approximationsklassen

In diesem dritten Teil der Vorlesung wollen wir unser Augenmerk nicht mehr inerster Linie auf die unterschiedlichen algorithmischen Techniken zum Entwurf vonNaherungsalgorithmen richten, sondern vielmehr Versuche unternehmen, Problemebezuglich ihrer Approximierbarkeit zu klassifizieren.Dabei werden wir insbesondere eine feinere Struktur innerhalb der Klasse NPOentdecken.

In gewisser Weise gehort dieser Vorlesungsteil also zum Gebiet der so genannten(strukturellen) Komplexitatstheorie. Daher wird in der Vorlesung mit dem Titel

”Komplexitatstheorie“ auch auf diese Aspekte von Naherungsalgorithmen eingegan-gen. Wir werden aber auch in diesem Zusammenhang nicht nur die Phanomenologieder Komplexitatsklassen betrachten, sondern unser Augenmerk weiterhin auf dasFinden von Naherungsalgorithmen richten.

10 ABSOLUTE APPROXIMATION 71

10 Absolute Approximation

Wir hatten am Anfang bereits bemerkt, dass die Betrachtung der absoluten Naherungsgutemeist sinnlos ist. Wir werden dies in diesem kurzen Kapitel naher begrunden.

Absoluter Fehler

Gegeben sei ein Optimierungsproblem P. Dann ist fur jede Instanz x von P undjede zulassige Losung y von x der absolute Fehler von y bezuglich x definiert als

D(x, y) := |m∗(x)−m(x, y)|

Dabei ist wiederum m∗(x) der Wert einer optimalen Losung der Instanz x undm(x, y) sei der Wert der Losung y.Ist A ein Approximationsalgorithmus fur P, d.h. gilt

∀x ∈ IP : A(x) ∈ SP(x),

so heißt A absoluter Approximationsalgorithmus, wenn es eine Konstante Kgibt, so dass fur alle x ∈ IP : D(x,A(x)) ≤ K gilt.

Statt Approximationsalgorithmus sagen wir auch oft Naherungsalgorithmus.

Beispiele: Es gibt nur wenige Beispiele fur NPO-Probleme mit absoluten Naherungs-algorithmen. Ein solches Beispiel liefert das Problem des Farbens von planarenGraphen.Betrachten wir dazu folgendes Korollar aus dem Beweis von Satz 5.15:

Satz 10.1 Betrachte die Knotenmenge des Eingabegraphen G = (V,E) als geord-net: (v1, . . . , vn). (Dies ist auch die Reihenfolge, in der die Partitionsheuristik ar-beitet.)Es sei Gi = G({v1, . . . , vi}); di(v) bezeichne den Grad von v in Gi.Die Partitionsheuristik benotigt dann hochstens

1 + max1≤i≤n

di(vi)

viele Farben zum Farben von Gi. 2

Wir wollen jetzt die Ordnung der Knoten genauer festlegen:vn sein ein Knoten minimalen Grades in G = (V,E).Induktiv gehen wir davon aus, die Reihenfolge (vi+1, . . . , vn) sei bereits festgelegt.Dann sei vi ein Knoten minimalen Grades in G(V \ {vi+1, . . . , vn}).

Satz 10.2 Ist G ein planarer Graph, so benotigt die Partitionsheuristik mit dersoeben definierten Knotenordnung hochstens 6 Farben zum Farben von G.


Beweis: Wegen Satz 10.1 reicht es zu zeigen, dass

max{di(vi) | 1 ≤ i ≤ n} ≤ 5.

Dazu ein kleiner Exkurs:

Wir erinnern wir an denEulerschen Polyedersatz: Fur planare Graphen gilt:

f −m + n = 2.

Dabei ist:f = # Flachen des (als eingebettet gedachten) Graphen,m = # Kanten,n = # Knoten.Daraus folgt: m ≤ 3n− 6 .Bezeichnet namlich li die Anzahl der an Flache Fi angrenzenden Kanten, so gilt,da ∀i(li ≥ 3):

2m =f∑

i=1

li ≥ 3f = 3m− 3n + 6.

Daher gilt:(∗) Jeder planare Graph enthalt wenigstens einen Knoten von Grad ≤ 5.Sonst ware 2m =

∑ni=1 d(vi) ≥ 6n, also m ≥ 3n, im Widerspruch zum soeben

Hergeleiteten.

Aus (∗) ergibt sich ∀i : di(vi) ≤ 5, da stets ein kleinstgradiger Knoten vi in Gi =G({v1, . . . , vi}) ausgewahlt wird und alle Gi planar sind, weil G = Gn planar ist unddie planaren Graphen unter der Operation ”Fortlassen von Knoten und inzidentenKanten“ abgeschlossen sind. 2

Folgerung 10.3 Das Satz 10.2 zu Grunde liegende Verfahren ist ein absoluter Ap-proximationsalgorithmus zum Farben planarer Graphen. Die absolute Fehlerschran-ke von 5 lasst sich noch auf 3 reduzieren, da 2-farbbare Graphen mit einer Greedy-Strategie optimal gefarbt werden konnen. 2

Im Allgemeinen sind aber keine absoluten Naherungsgarantien zu erwarten. Schondas (approximationsalgorithmisch relativ einfache) Rucksackproblem gestattet (wohlhochstwahrscheinlich) kein polynomielles Naherungsverfahren mit konstantem ab-soluten Fehler. Genauer gilt:

Satz 10.4 Unter der Annahme P 6= NP gilt:Es gibt keinen polynomiellen absoluten Approximationsalgorithmus fur Maximum-Knapsack.


Beweis: Es sei X eine Menge Gegenstande sowie zugehorigen Profiten pi undGroßen ai und b die Rucksackkapazitat. Gabe es einen polynomiellen absoluten Ap-proximationsalgorithmus fur MaximumKnapsack mit Fehlerschranke K, so konntenwir das Rucksackproblem in Polynomzeit wie folgt losen:

Wir generieren eine neue Instanz, indem wir alle Profite mit (K +1) multiplizieren.Die Menge der zulassigen Losungen wird dadurch nicht verandert. Der Wert jederLosung ist nun aber ein Vielfaches von K + 1, was zur Folge hat, dass jede Losungmit absolutem Fehler K bereits optimal ist. 2

Ahnliche Argumente lasen sich fur viele andere Probleme angeben.

11 RELATIVE APPROXIMATION; DIE KLASSE APX 74

11 Relative Approximation; die Klasse APX

11.1 Definitionen der Grundbegriffe

Interessanter Weise sind die in der Literatur (wenigstens) zwei verschiedene Maßegangig, um die relative Gute von Naherungsverfahren anzugeben.

Definition 11.1 Ist P ein Optimierungsproblem, so ist —fur jede Instanz x vonP und fur jede zulassige Losung y von x— der relative Fehler von y bezuglich xdefiniert als

E(x, y) :=|m∗(x)−m(x, y)|

max{m∗(x),m(x, y)}=

D(x, y)max{m∗(x),m(x, y)}

.

Ist A ein Approximationsalgorithmus fur P, so heißt A ε-Approximation, wenn

∀x ∈ IP : E(x,A(x)) ≤ ε.

Bemerkung 11.2 Der relative Fehler ist gleich Null, wenn die Losung optimal ist,und er liegt nahe bei Eins, wenn die Losung schlecht ist.

Definition 11.3 Ist P ein Optimierungsproblem, so ist —fur jede Instanz x vonP und fur jede zulassige Losung y von x— die Leistungsgute (engl: performanceratio) von y bezuglich x definiert als

R(x, y) := max{

m∗(x)m(x, y)

,m(x, y)m∗(x)

}.

Ist A ein Approximationsalgorithmus fur P, so heißt A r-Approximation, wenn

∀x ∈ IP : R(x,A(x)) ≤ r.

Bemerkung 11.4 Die Leistungsgute ist gleich Eins, wenn die Losung optimal ist,und sie ist sehr groß, wenn die Losung schlecht ist. Offenbar gilt:

E(x, y) = 1− 1R(x, y)

.

Ist namlich P ein Maximierungsproblem, so ist:

1− 1R(x, y)

= 1− 1m∗(x)m(x,y)

= 1− m(x, y)m∗(x)

=m∗(x)−m(x, y)

m∗(x).

Ist P ein Minimierungsproblem, so gilt:

1− 1R(x, y)

= 1− m∗(x)m(x, y)

=m(x, y)−m∗(x)

m(x, y).


Hinweis: entspricht r-Approximation aus Kapitel 2 !

Beispiel 11.5 Die (diversen) Naherungsalgorithmen fur das Knotenuberdeckungs-problem sind sowohl 1

2 -Approximation (im Sinne des relativen Fehlers) als auch2-Approximation (im Sinne der Leistungsgute).

Definition 11.6 P heißt ε-approximatierbar (bzw. r-approximierbar), wennes eine Polynomzeit-ε-Approximation (bzw. r-Approximation) fur P gibt.

Bemerkung 11.7 Algorithmen A, die (im Minimierungsfall)

mA(x, y) ≤ r ·m∗(x) + k

erfullen, sind ”nur“ (r +k)-Approximationen (im Sinne von Definition 11.3), wer-den aber oft als r-Approximationen in der Literatur angesprochen. Wir werden sol-che Algorithmen asymptotische r-Approximationen nennen. Im Zusammen-hang mit Approximationsschemata ist dieser Unterschied bedeutender, siehe Kapi-tel 12 und 14.

Definition 11.8 APX ist die Klasse aller NPO-Probleme, die r-approxi-mierbar fur ein r ≥ 1 sind.

In den vorigen Abschnitten haben wir bereits einige Probleme aus APX kennengelernt. Wir wollen an dieser Stelle noch ein weiteres Problem erortern.

11.2 MAXSAT

I : Menge C von Klauseln uber einer Menge V von Variablen(Eine Klausel ist eine Disjunktion von Literalen.Ein Literal ist eine Variable oder ihre Negation.Formal ist C als Menge von Mengen von Literalen aufzufassen.)

S : Menge der Wertzuweisungen f : V → {true, false}m : |{c ∈ C | f(c) = true}|opt : max

Beispiel: Die KNF-Formel (x ∨ y) ∧ (x ∨ y) wurden wir als C = {{x, y}, {x, y}}schreiben.

Wir analysieren den folgenden Greedy-Algorithmus:

GreedySAT(C, V )

1. Fur alle v ∈ V setze f(v) := true (Anfangsbelegung);

2. Wiederhole, solange C 6= ∅:


2a. Es sei l ein Literal, das in einer maximalen Zahl von Klauseln vorkommt;es sei x die zugehorige Variable.

2b. Bestimme die Menge Cx von Klauseln, in denen x vorkommt.

2c. Bestimme die Menge Cx von Klauseln, in denen x vorkommt.

2d. Ist l = x, so

2d(i) C := C \ Cx;2d(ii) Losche x aus allen Klauseln in Cx \ Cx

2d(iii) Losche alle leeren Klauseln aus C.

2e. sonst:

2e(0) f(x) := false;2e(i) C := C \ Cx;2e(ii) Losche x aus allen Klauseln Cx \ Cx;2e(iii) Losche alle leeren Klauseln aus C.

3. Liefere f zuruck.

Satz 11.9 GreedySAT ist eine Polynomzeit-2-Approximation fur MAXSAT.

Beweis: Per Induktion uber die Anzahl der Variablen zeigen wir:Ist eine Instanz mit c Klauseln gegeben, so liefert GreedySAT stets eine Losung,die mindestens c/2 der Klauseln erfullt. Da trivialerweise c eine obere Schranke furden Wert einer optimalen Losung ist, folgt so die Behauptung.Im Fall, dass es nur eine Variable gibt, folgt die Behauptung trivialerweise. Es wer-de nun angenommen, die Behauptung sei fur n − 1 Variablen (n > 1) bewiesen.Von GreedySAT werde als erstes die Variable x betrachtet. Es seien cx bzw. cx dieAnzahl der Klauseln, in denen x bzw. x vorkommen. Ohne Einschrankung betrach-ten wir cx ≥ cx, d.h., GreedySAT wird x auf true setzen. Nach dieser Zuweisungmussen (nach Schritt 2d(i) bzw. 2d(iii)) noch c ≥ c − cx − cx viele Klauseln (mitn − 1 Variablen) betrachtet wurden. Nach Induktionsvoraussetzung werden dahervon GreedySAT wenigstens c/2 ≥ (c − cx − cx)/2 der c vielen Klauseln erfullt.Insgesamt werden daher wenigstens cx + (c − cx − cx)/2 = c+cx−cx

2 ≥ c2 Klauseln

der ursprunglichen Klauselmenge erfullt. 2

Andererseits gibt es auch Probleme, die hochstwahrscheinlich nicht zu APX gehoren,wie der folgende Satz zeigt.

11.3 Das Handelsreisendenproblem MTS

Satz 11.10 Wenn das allgemeine Handelsreisendenproblem MTS zu APX gehorte,dann ware P = NP.

Beweis: Wir beweisen das Resultat duch Reduktion vom Hamiltonschen Kreispro-blem. Ein Hamiltonscher Kreis ist dabei eine Permutation (v1, . . . vn) der Knoteneines ungerichteten Graphen G = (V,E), |V | = n, sodass ∀1 ≤ i ≤ n{vi, vi+1} ∈ E


(der Einfachheit halber sei vn+1 = v1). Fur jedes r ≥ 1 konstruieren wir eine In-stanz von MTS derart, dass aus der Existenz einer r-Approximation fur MTS fol-gen wurde, dass es einen Polynomzeitalgorithmus zum Hamiltonschen Kreisproblemgabe. Da das Hamiltonsche Kreisproblem NP-vollstandig ist, folgt die Behauptung.Geben wir uns also ein r ≥ 1 vor. Ist G = (V,E) eine Hamiltonsche Kreisproble-minstanz, so definieren wir (auf derselben Knotenmenge V ) eine Abstandsfunktiond, die zusammen mit V das fragliche MTS-Problem angibt. Setze dazu:

d(u, v) :={

1, {u, v} ∈ E1 + |V | · r, {u, v} /∈ E

MTS hat eine (minimale) Losung vom Wert |V | gdw. G einen Hamiltonschen Kreisenthalt.Eine r-Approximation A fur MTS konnte wie folgt zum Losen des HamiltonschenKreisproblems verwendet werden:

• LiefertA einen Wert ≤ r·|V | zuruck, so hatte das ursprungliche Kreisproblemeine Losung.

• Liefert A einen Wert > r · |V | zuruck, so war das ursprungliche Kreisproblemunlosbar. 2

Korollar 11.11 Ist P 6= NP, so ist APX 6= NPO. 2

Interessanterweise verringert sich (approximationstheoretisch betrachtet) die Kom-plexitat von MTS, wenn man sich auf metrische Instanzen einschrankt. Cristofidesersann einen Algorithmus fur MMTS (metrisches MTS), der eine Leistungsgute von3/2 gewahrleistet. Diesen wollen wir nun kennen lernen (und dabei den Greedy-Algorithmus aus Kapitel 4 essentiell verbessern).Dazu benotigen wir ein paar weitere graphentheoretische Begriffe und graphenal-gorithmische Ergebnisse.

Ein Multigraph ist ein Paar M = (V,E), wobei V eine endliche Knotenmengeist und F eine Multimenge von Kanten. Eine Multimenge von Kanten (uber V) istdabei (vereinfacht) eine Abbildung F : {{u, v} | u, v ∈ V } → N0; sogenannte ”Mehr-fachkanten“ sind also zugelassen. Wir werden im Folgenden auch Multigraphen mitKantengewichten betrachten; dabei wird jeder einzelnen Kante e = ({u, v}, j),j ≤ F ({u, v}) ein Gewicht c(e) zugeordnet. Man sagt, ein Graph G = (V,E)mit Kantengewichten erfulle die 4-Ungleichung, wenn ∀u, x, v ∈ V : c ({u, v}) ≤c ({u, x})+ c ({x, v}), falls {u, v}, {u, x}, {x, v} ∈ E. Eine Folge von Knoten f ∈ V ∗

heißt Eulersch, wenn jedes v ∈ V mindestens einmal in f vorkommt, der ersteKnoten von f gleich dem letzten ist und fur alle Zerlegungen f = xuvy, u, v ∈ Vgilt: F ({u, v}) ≥ 1, sowie

∀u, v ∈ V, u 6= v : F ({u, v}) = |{x ∈ V ∗ | ∃y ∈ V ∗ : f = xuvy ∨ f = xvuy}| .

Mit anderen Worten: jede Kante des Multigraphen wird genau einmal durchlaufen.Ein Multigraph heißt Eulersch, wenn es eine Eulersche Knotenfolge gibt.


Mitteilung 11.12 Ein Multigraph ist genau dann Eulersch, falls alle seine Knoten(zusammenhangen und) geraden Grad besitzen.

Es gibt einen Polynomzeitalgorithmus, der entscheidet, ob ein gegebener MultigraphEulersch ist und dabei auch eine zugehorige Knotenfolge konstruiert.

Lemma 11.13 Ist G = (V,E) ein vollstandiger Graph mit Kantengewichten mitGewichtsfunktion c, der die 4-Ungleichung erfullt und ist M = (V, F ) irgendeinEulerscher Multigraph mit der selben Knotenmenge derart, dass alle Kanten zwi-schen zwei beliebigen Knoten {u, v} ⊆ V das Gewicht c ({u, v}) haben, dann findetman in Polynomzeit eine Tour I in G mit einem Wert, der hochstens gleich derSumme der Gewichte der Kanten in M ist.

Beweis: Es sei V = {v1, . . . , vn}. Per Definition ist die Summe der Gewichte allerKanten, die in einer Eulerschen Knotenfolge ”vorkommen“, gleich der Summe derGewichte der Kanten in M .Wir bestimmen als eine Eulersche Knotenfolge f = vi1 . . . vim

in M . Es sei j(r) dererste Index in 1, . . . ,m mit vij(r) = vr, 1 ≤ r ≤ n. Wir gehen davon aus, dass diev1, . . . , vn so sortiert sind, dass

j(1) ≤ j(2) ≤ · · · ≤ j(n)

gilt. Wegen der 4-Ungleichung gilt:

∀1 ≤ r ≤ n : c({vr, v(r+1 mod m)+1}) = c({

vij(r) , vi(j(r+1) mod m)+1

})≤ c

({vij(r) , vij(r) mod m+1

})+({

vij(r) mod m+1 , vij(r) mod m+2

})+ . . .

. . . +({

vij(r+1) mod m, vij(r+1) mod m+1

})Fur die Tour vij(1) , . . . , vij(n) gilt daher die Behauptung. 2

Ein Matching in einem Graphen ist eine Kantenmenge, in der keine zwei Kanteneinen gemeinsamen Endpunkt haben.In der Standard-Algorithmenvorlesung wird ein Polynomzeitalgorithmus zum Auffin-den großtmoglicher (Maximum) Matchings vorgestellt. Ein Matching heißt perfekt,wenn jeder Knoten des Graphen Endpunkt einer Kante aus dem Matching ist.Es gibt einen Polynomzeitalgorithmus zum Auffinden minimaler perfekter Mat-chings, wobei ”Minimalitat“ im Sinne der jetzt angenommenen Kantengewichtedes Graphen zu sehen ist.

Wir stellen jetzt den Algorithmus von Christofides vor.

MMTS-CHR(G = (V,E), c) (G vollstandiger Graph, c Kantengewichtsfunktion)

1. Finde einen (bzgl. c) minimalen Spannbaum T = (V,ET ) von G.

2. Es sei U ⊆ V die Menge der Knoten in T mit ungeradem Grad.

3. Finde ein (bzgl. c) minimales perfektes Matching H in G[U ].


4. Bilde den Multigraphen M = (V,ET + H).(In M gibt es nur Einfach- oder Doppelkanten.)

5. Finde eine Eulersche Knotenfolge f in M .

6. Bilde (wie in obigem Lemma) eine Tour I aus f .

7. Liefere I zuruck.

Satz 11.14 Ist (G = (V,E), c) eine Instanz von MMTS, so liefert MMTS-CHR inPolynomzeit eine Losung mit Leistungsgute ≤ 3

2 .

Beweis: Mit obigen Vorbemerkungen und Grundkenntnissen aus einer Algorith-menvorlesung ist klar, dass MMTS-CHR in Polynomzeit arbeitet. Wir zeigen jetztdie Leistungsguteschranke:Dazu betrachten wir den Multigraph M = (V,ET + H) und eine Eulersche Kno-tenfolge f . (Beachte: M ist Eulersch wegen obiger Mitteilung!). Nach dem vorigenLemma konnen wir eine Tour I finden, die

m(G, I) ≤ c(ET ) + c(H)

genugt. Im Folgenden schatzen wir c(ET ) und c(H) nach oben mit Hilfe von m∗(G)ab.

Behauptung 1:

c(H) ≤ m∗(G)2

.

Beweis: Es sei (vi1 , . . . , vi|U|) die Folge der Knoten aus U in der Reihenfolge, inder sie in einer fixierten optimalen Tour I∗ vorkommen.Offensichtlich sind

H1 ={(vi1 , vi2), . . . , (vi|U|−1 , vi|U|)

}und

H1 ={(vi2 , vi3), . . . , (vi|U|−2 , vi|U|−1), (vi|U| , vi1)

}perfekte Matchings. Wegen der Gultigkeit der 4-Ungleichung gilt:

c(H1) + c(H2) ≤ m∗(G) = c(I∗).

Da H ein perfektes Matching mit minimalem Gewicht ist, gilt c(H) ≤ c(H1) undc(H) ≤ c(H2), also gilt 2c(H) ≤ m∗(G).

Behauptung 2:c(ET ) ≤ m∗(G).

Hierzu beobachte man: Eine (optimale Tour) ist ein Spannbaum (ein ”Spannpfad“)plus einer zusatzlichen Kante. Da T minimaler Spannbaum ist, gilt die Behauptung.Zusammengenommen haben wir gezeigt:

m(G, I) ≤ m∗(G) +m∗(G)

2=

32m∗(G).

2

Wir wollen den Algorithmus an einem praktischen Beispiel verdeutlichen:

Gegeben sei folgende Straßen-km-Entfernungstabelle zwischen den Stadten Amster-dam, Berlin, Genf, Mailand, Prag, Rom, Warschau und Wien:


AMS 685 925 1180 960 1755 1235 1180BER 1160 1105 340 1530 585 630

GEN 325 950 880 1575 1025MAI 870 575 1495 830

PRA 1290 625 290ROM 1915 1130

WAR 765WIE

��

��

��

��

��

��

��

��

��

Rom

Amsterdam Berlin Warschau

Prag

WienGenf

Mailand

Abbildung 1: Ein minimaler Spannbaum

��

��

��

��

��

��

��

��

Rom


Prag

WienGenf

Mailand

Abbildung 2: Der so erzeugte Multigraph

Die Bilder 1, 2 und 3 zeigen die drei Hauptphasen des Algorithmus: Schritt 1, 4und 6. Als Eulersche Knotenfolge nehmen wir dabei


AMS-BER-WAR-BER-PRA-WIE-MAI-ROM-MAI-GEN-AMS

Eine optimale Tour finden Sie in Bild 4. Diese ist nicht durch bloßes zyklischesVerschieben der Eulerschen Knotenfolge zu erzielen, da die Kante Wien-Rom bereitsim Spannbaum fehlt.

Schließlich wollen wir die asymptotische Scharfe der fur den Algorithmus vonChristofides gefundene Schranke nachweisen.

Dazu betrachte man die in Abbildung 5 angegebene Instanzenschar Gn von MMTS.Neben den angegebenen Bemeßungen beachte man, dass der Winkel zwischen a1an+1

sowie a1b1 (und ebenso der zwischen a1b1 und b1a2, usw.) 60◦ betragt; anson-sten verstehe man das Beispiel als ein in der Euklidischen Ebene befindliches. Einmoglicher minimaler Spannbaum besteht aus der in Abbildung 5 angegebenen Tour(ohne die Kante {a1, an+1}).

Ausgehend von diesem Spannbaum bestimmt MMTS-CHR die in (3) angegebeneTour vom Wert 3n + 2ε.Der Wert der in (4) angegebenen (optimalen) Tour betragt aber lediglich 2n+1+4ε.

Bemerkung 11.15 Bis heute wurde kein besserer Approximationsalgorithmus (”bes-ser“ nur im Sinne der Approximationsgute) gefunden als MMTS-CHR fur den me-trischen Fall. Beschrankt man sich jedoch weiter auf den Euklidischen Fall, so gibtes sogar ein PTAS (→ nachstes Kapitel).

11.4 Grenzen der Approximierbarkeit — Die Gap-Technik

Die in Satz 11.10 kennen gelernte Beweistechnik lasst sich wie folgt allgemeinerdarstellen.

Satz 11.16 Es seien P ′ ein NP-vollstandiges Entscheidungsproblem und P einMinimierungsproblem aus NPO. Angenommen, es gibt zwei in Polynomzeit bere-chenbare Funktionen

f : IP′ → IP und

c : IP′ → N sowie

eine Konstante gap > 0, sodass fur jede Instanz x von P ′ gilt:

m∗(f(x)) ={

c(x), x ist positive Instanz von P ′c(x)(1 + gap), sonst.

Dann gibt es keine Polynomzeit-r-Approximation fur P mit r < 1 + gap, fallsP 6= NP gilt.

Beweis: Nehmen wir an, es gabe solch eine r-Approximation A, r < 1 + gap, furP. Wir konnen den Polynomzeitalgorithmus A wie folgt dazu benutzen, um P ′ inPolynomzeit zu losen:


A′(x):10

1. Berechne f(x).

2. Berechne y := A(f(x)).

3. Berechne c := c(x).

4. Gilt m(f(x), y) < c · (1 + gap), so antworte JA!

5. Gilt m(f(x), y) ≥ c · (1 + gap), so antworte NEIN!

Warum ist A′ korrekt?

Ist x eine positive Instanz von P ′, so gilt nach Voraussetzung

m(f(x), y)c

=m(f(x), y)m∗(f(x))

≤ r < 1 + gap

A′ antwortet in diesem Fall also richtig (Schritt 4.).

Ist x eine negative Instanz von P ′, so gilt nach Voraussetzung

m(f(x), y) ≥ m∗(f(x)) = c · (1 + gap),

sodass A′ auch in diesem Fall korrekt antwortet (Schritt 5.). 2

11.5 Anwendung auf das Graphenfarbeproblem

Mitteilung 11.17 Fur planare Graphen (die nach dem Vierfarben-Satz ja 4-farbbar sind) ist die Frage nach der 3-Farbbarkeit NP-vollstandig.

Daher gilt: Das (allgemeine sowie das auf planare Graphen eingeschrankte) Gra-phenfarbeproblem lasst sich nicht besser als mit Faktor r < 4/3 approximieren.(gap = 1/3)

Man kann hier sogar noch mehr zeigen:

Mitteilung 11.18 Gilt P 6= NP, so liegt MinimumGraphColoring in NPO \APX.

10x ist eine Instanz von P ′.


��

��

��

��

��

��

��

��

Rom


WienGenf

Mailand

Prag

Abbildung 3: Die von Christofides erhaltene Tour I (vom Wert 5395)

��

��

��

��

��

��

��

��

Mailand


WienGenf

Prag

Rom

Abbildung 4: Ein optimale Tour I∗ (vom Wert 5140)


��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

ε1+

bbbb1 2 3 n

a a a an432

ε1+

a a a an432

a a1 n+1

bbbb1 2 3 n

1

1

1

1

1(a)The approximate tour

(b)The optimal tour

��

��

��

Abbildung 5: Zur Scharfe von Christofidis

12 POLYNOMZEIT-APPROXIMATIONSSCHEMATA 85

12 Polynomzeit-Approximationsschemata

Wir hatten im vorigen Kapitel Beispiele fur Probleme kennen gelernt, die sich nichtmit konstantem Faktor approximieren lassen (sofern nicht P = NP) und fur Proble-me, die sich nicht mit beliebigem Faktor approximieren lassen (wie Graphenfarbenauf planaren Graphen). Jetzt wollen wir uns Probleme ansehen, die beliebig genaueApproximationsverfahren gestatten, wobei eine erhohte Genauigkeit der Naherungjedoch durch eine erhohte Laufzeit eingehandelt wird.

Definition 12.1 Es sei P ∈ NPO. Ein Algorithmus A heißt Polynomzeit-Approximationsschema(engl: polynomial-time approximation scheme, kurz PTAS), falls A fur jedes Paarvon Eingaben (x, r), x Instanz von P und r > 1, eine r-approximative Losungzuruck liefert in einer Zeit, die polynomiell in |x| ist (aber moglicherweise nicht-polynomiell in 1

r−1).Die zugehorige Problemklasse nennen wir PTAS.

12.1 Kleinstmogliche Zweiteilung (Minimum Partition, MP)

Problembeschreibung:

I : Endliche Menge X von Gegenstanden, zu jedem xi ∈ X ein Gewicht ai ∈ N.S : {Y1, Y2 ⊆ X | Y1 ∩ Y2 = ∅, Y1 ∪ Y2 = X}m : max

{∑xi∈Y1

ai,∑

xi∈Y2ai

}opt : min.

Es ist klar, dass MP in APX liegt, denn die Zweiteilung (X, ∅) ist trivialerweiseeine 2-Approximation.

Wir zeigen jetzt:

Satz 12.2 MP ∈ PTAS.

Beweis: Betrachte dazu das folgende Programm:

MP-PTAS(X, a, r)

1. Ist r ≥ 2, so liefere (X, ∅).

2. Sortiere X absteigend bzgl. ihrer Gewichte.Es sei (x1, . . . , xn) die so erhaltene Folge.

3. k(r) :=⌈

2−rr−1

⌉;

4. Finde eine optimale Zweiteilung (Y1, Y2) fur (x1, . . . , xk(r)).

5. Fur j := k(r) + 1 bis n tue


5a. Falls ∑xi∈Y1

ai ≤∑

xi∈Y2

ai,

5b. soY1 := Y1 ∪ {xj} ,

5c. sonstY2 := Y2 ∪ {xj} .

6. Liefere (Y1, Y2).

Klar ist: Die Laufzeit von MP-PTAS ist fur festes r polynomiell in n; allerdingsfuhrt Schritt 4 zu exponentieller Laufzeit in k(r) mit k(r) ∈ O

(1

r−1

).

Wir zeigen nun, dass die Leistungsgute, gegeben x = (X, a) und r > 1, durch rbeschrankt ist. Klar ist dies, falls r ≥ 2. Sei nun also r ∈ (1, 2). Setze a(Y ) :=∑

xj∈Y aj , Y ⊆ X und L := a(X)2 . O. E. sei a(Y1) ≥ a(Y2), und xh das letzte

Element, das zu Y1 hinzugefugt wurde durch MP-PTAS.

Also ist a(Y1)− ah ≤ a(Y2)

; 2 · a(Y1)− ah ≤ a(Y1) + a(Y2) = 2L

; a(Y1)− L ≤ ah

2(∗)

Wurde xh bereits in Schritt 4 eingefugt, so liefert MP-PTAS sogar eine optimaleLosung.Wurde xh in Schritt 5 eingefugt, so haben wir (naturlich) ah ≤ aj fur 1 ≤ j ≤ k(r)(absteigende Sortierung!) und

2L ≥∑

1≤j≤h

aj ≥ h · ah ≥ (k(r) + 1) · ah. [+]

Wegen a(Y1) ≥ L ≥ a(Y2) und m∗(x) ≥ L gilt ferner:

a(Y1)m∗(x)

≤ a(Y1)L

(∗)≤ 1 +

ah

2L

[+]

≤ 1 +1

k(r) + 1≤ 1 +

12−rr−1 + 1

= r.

2

Im Abschnitt uber Dynamisches Programmieren hatten wir ein PTAS fur Maxi-mumKnapsack kennen gelernt, das ebenfalls darauf beruht, fur eine (geeignet ver-standene) ”Subinstanz“ eine optimale Losung zu bestimmen und diese dann (ge-eignet modifiziert) als Losung des ursprunglichen Problems zu betrachten.Diese Vorgehensweise ist typisch fur die Entwicklung von PTAS. Wir wollen hierzunoch ein Beispiel aus nderen Bereichen studieren, zunachst das Problem, großtmogli-che unabhangige Mengen in planaren Graphen zu finden.

Dazu benotigen wir noch einige Begriffe:

Es sei eine planare Einbettung (also eine ”Zeichnung“ in der Ebene) eines plana-ren Graphen G gegeben. Die Schicht eines Knotens von G ist induktiv wie folgtbestimmt:


1. Alle Knoten, die an die außere Flache grenzen, gehoren zur Schicht 1.

2. Fur jedes i > 1 seien die Knoten der Schicht 1, . . . , i−1 bekannt; wir entfernendiese (in Gedanken) aus dem eingebetteten Graphen. Alle Knoten, die nunan die außere Flache grenzen, gehoren zur Schicht i.

Die Anzahl der Schichten eines eingebetteten Graphen heißt auch seine Außerpla-naritat.

v

v

v

v

v

v1

4

7

10

13

16

v9

v6

v3

v18

v15

v12

v

v

v

v

v

v

2

5

8

11

14

17

Abbildung 6:

Abbildung 6 zeigt die planare Einbettung eines Graphen mit sechs Schichten. SolcheEinbettungen konnen aber sehr viel komplizierter werden, mit Antennen, meheren

”Zentren“ etc.

B. S. Baker konnte zeigen:

Mitteilung 12.3 Ist K die Außerplanaritat eines eingebetteten Graphen G mit nKnoten, so kann eine großtmogliche unabhangige Menge fur G in Zeit O(8K · n)bestimmt werden.

Dieses Resultat verwendete sie, um ein PTAS fur MIS (auf planaren Graphen)anzugeben, welches wir jetzt vorstellen.

Satz 12.4 MIS (auf planaren Graphen) ∈ PTAS.

Beweis: Betrachte dazu das folgende Programm:

MIS-PTAS (G = (V,E), r)

1. Setze K := d1/(r − 1)e.

2. Bestimme eine planare Einbettung von G.


3. Berechne die Knotenschichten.(Sei Vi die Menge der Knoten auf Schicht i.)

4. Fur i = 0 bis K tue

4a. Sei Vi die Vereinigung aller Vj mit j ≡ i mod K + 14b. Gi := G(V \ Vi)

(Gi hat Außerplanaritat K)4c. Berechne großtmogliche unabhangige Mengen Ii von Gi.

5. Sei Im(m = 0, . . . ,K) derart, dass |Im| = max{|Ii| | 0 ≤ i ≤ K}.6. Liefere Im zuruck.

Es sei r > 1 die angestrebte Approximationsgute und setze K :=⌈

1r−1

⌉. Sei ein

eingebetteter Graph G gegeben. Wahle Vi, Vi, Gi wie im Programm. Nach Kon-struktion (jede K +1 Schicht ist entfernt worden!) ist jedes Gi K-außerplanar. Einegroßtmogliche unabhangige Menge Ii von Gi kann in Zeit O(8K · n) (gemaß obigerMitteilung) gefunden werden. Es sei Im eine Menge großtmoglicher Machtigkeitunter den I0, . . . , IK .Bezeichne nun I∗ eine großtmogliche unabhangige Menge von G. Es gibt dann einr, 0 ≤ r ≤ K, mit

∣∣Vr ∩ I∗∣∣ ≤ |I∗| /(K + 1). Da Ir eine großtmogliche unabhangige

Menge auf Gr ist, gilt:

|Ir| ≥ |V \ Vr ∩ I∗|= |I∗ \ (Vr ∩ I∗)|

≥ |I∗| − |I∗|K + 1

=K

K + 1|I∗|

Also ist|Im| ≥ |Ir| ≥

K

K + 1|I∗|

Daraus folgt: R(G, Im) = I∗

Im≤ K+1

K ≤ r. 2

12.2 Das Kreisscheibenuberdeckungsproblem (Disc Cover)

Eine ahnliche Strategie wie Baker ersannen (in etwa gleichzeitig) D. S. Hochbaumund W. Maas fur Uberdeckungs- und Packungsprobleme in so genannten geometri-schen Graphen.Wir werden hier konkret das Uberdeckungsproblem einer gegebenen n-Punktmengeder Euklidischen Ebene mit Hilfe von Kreisscheiben vom (einheitlichen) Durchmes-ser D betrachten.

I = {(xi, yi) | 1 ≤ i ≤ n} ⊆ R2 (, D)S : {D = {D1, . . . , DK} |

⋃Ki=1 Di ⊇ I}

Di Kreisscheibe vom Durchmesser D.m : K = |D|opt : min.


Um dieses Problem anzugehen, treffen wir zunachst einige Vereinbarungen:

Wir gehen davon aus, die Punkte aus I liegen alle in einem Rechteck R ⊆ R2. Desweiteren sei l der so genannte Verschiebeparameter (dessen Bedeutung weiterunten klar werden wird).In einer ersten Phase unterteilen wir R in vertikale Streifen der Breite D; jederStreifen sei links offen und rechts abgeschlossen. Wir betrachten stets Gruppen vonl aufeinander folgenden Streifen, also Makrostreifen der Breite l ·D, abgesehen vonevtl. schmaleren ”Randstreifen“. Offenbar lasst sich R in l verschiedene Weisen inMakrostreifen unterteilen; M1, . . . ,Ml seien die entsprechenden Makrostreifenmen-gen.Es sei A ein Algorithmus, der eine zulassige Losung fur Streifen der Maximalbreitel ·D berechnet. Fur eine Makrostreifenmenge Mi sei A(Mi) der Algorithmus, derA auf jeden Makrostreifen aus Mi anwendet und die Vereinigung der so erhaltenenKreisscheibenmengen als Losung liefert; diese ist sicherlich zulassig.Der Verschiebealgorithmus SA liefert nun eine solche Losung, die minimal unterden Losungen von A(M1), . . . ,A(Ml) ist.Es seien ferner rA und rSA die Leistungsguten (performance ratios) von A und SA.Dann gilt:

Lemma 12.5 Das Verschiebelemma:

rSA ≤ rA

(1 +

1l

).

Beweis: Per Definition ist

mA(Mi) =∑

J∈Mi

mA(J) ≤ rA ·∑

J∈Mi

m∗(J).

Dabei seien mA(J) bzw. m∗(J) der von Algorithmus A bzw. einem optimalen Al-gorithmus gelieferte Wert, angewendet auf die durch den Makrostreifen J gegebeneSubinstanz.Es sei S∗ eine optimale Losung des Ausgangsproblems vom Wert m∗. Es sei S∗[i] ⊆S∗ diejenige Menge von Kreisscheiben, die Punkte von I aus zwei angrenzendenMakrostreifen von Mi abdeckt.Offenbar gilt:

∀i, j : S∗[i] ∩ S∗[j] 6= ∅ → i = j [+]

Da m∗(J) der optimale Wert fur Streifen J ist, gilt:

m∗(J) ≤ |{D ∈ S∗ | D ∩ J 6= ∅}|

;∑

J∈Mi

m∗(J) ≤∑

J∈Mi

|{D ∈ S∗ | D ∩ J 6= ∅}|

= |S∗|+ |S∗[i]| ,


denn (nur) die Scheiben aus S∗[i] sind doppelt zu zahlen. Da das Minimum durchdas arithmetische Mittel majorisiert wird, gilt schließlich:

mSA = mini=1,...,l

mA(Mi) ≤1l

l∑i=1

mA(Mi)

≤ 1l

l∑i=1

rA ·∑

J∈Mi

m∗(J)

≤ rAl

l∑i=1

(|S∗|+ |S∗[i]|)

=rAl

(l ·m∗ +

l∑i=1

|S∗[i]|

)≤ rA

l(l + 1)m∗

2

Satz 12.6 Das Kreisscheibenuberdeckungsproblem liegt in PTAS.

Beweis: Durch zweimaliges (geschachteltes) Anwenden des Verschiebelemmas, wo-bei einmal das Ausgangsrechteck in vertikale und das andere Mal in horizontaleStreifen unterteilt wird, erhalten wir einen Algorithmus B mit

rB ≤ r2

(1 +

1l

)2

.

r2 sei dabei die Leistungsgute eines Algorithmus fur eine quadratische Flache dergroßtmoglichen Seitenlange l · D. Wir zeigen nun: r2 = 1 fur einen Algorithmus,der (lediglich) exponentiell in l ist.

Damit ist die Behauptung gezeigt, denn fur vorliegende Leistungsgute r brauchtnur ein l mit

(1 + 1

l

)2 ≤ r bestimmt zu werden.

Betrachte nun ein Quadrat der großtmoglichen Seitenlange l ·D, das mit Kreisschei-ben vom Durchmesser D abzudecken ist. Klar ist, dass man hochstens O(l2) vieleScheiben benotigt, um das vorliegende Quadrat luckenlos abzudecken. [+]Es sei im Weiteren n die Anzahl der (ursprunglich) vorgegebenen n Punkte, die imbetrachteten Quadrat liegen. Es sei x einer dieser Punkte. Wird x (in einer optima-len Uberdeckung) von einer Scheibe abgedeckt, die keinen anderen Punkt abdeckt,so ist die exakte Position dieser Scheibe im Grunde gleichgultig.Andernfalls gibt es noch andere Punkte, die von der selben Kreisscheibe abgedecktwerden. O.E. konnen wir annehmen, zwei dieser Punkte liegen auf dem Rand derScheibe. Da durch jene zwei Punkte nur zwei verschiedene Kreise gezogen werdenkonnen, die diese Punkte auf dem Rand liegen haben, gibt es insgesamt hochstens

2 ·(

n2

)= O(n2) viele Kreisscheibenpositionen zu berucksichtigen.

Wegen [+] sind an diesen Positionen (hochstens) O(l2) viele auszuwahlen, so dassinsgesamt maximal O(np(l)) viele Kreisscheibenanordnungen durchzutesten sind furein Polynom p. 2


12.3 Zum Zusammenhang mit der Konstruktion von Baker

Ist D eine Menge von Kreisscheiben, so ist D in naturlicher Weise der folgendeGraph zugeordnet. GD = (D, ED) mit {D1, D2} ∈ E gdw. D1 ∩D2 6= ∅.Diese geometrischen Graphen sind ein naheliegendes Modell fur viele reale Proble-me.

Mitteilung 12.7 (Satz von Koebe):Ein geometrischer Graph GD = (D, ED) ist planar, wenn ∀ {D1, D2} ∈ ED :|D1 ∩D2| = 1. Jeder planare Graph lasst sich umgekehrt als geometrischer Graphdarstellen, dessen Kreisscheiben sich paarweise in einem Punkt treffen (also sichnur beruhren).

Speziell kummern wir uns nun um Einheitskreisgraphen, das sind geometrischeGraphen mit Kreisscheiben vom Radius 1.

Satz 12.8 MIS —eingeschrankt auf Einheitskreisgraphen— liegt in PTAS.

Beweis: (Skizze) Wie in vorigem Satz unterteilt man ein die tangierten Punkte derEbene einschließendes Rechteck nacheinander in vertikale und horizontale Streifender Breite k. Es ist leicht einzusehen, dass eine unabhangige Menge von Einheits-kreisscheiben in einem Quadrat der Seitenlange k hochstens O(k2) viele Elementehat. Dies ermoglicht wiederum, MIS fur Quadrate der Seitenlange k optimal in ei-ner Zeit O(npol(k)) zu losen, wobei n die Zahl der gegebenen Kreisscheiben und polein Polynom ist.Indem wir jetzt (fur jeden vertikalen Streifen) alle Graphen Gi betrachten, derenStreifen-Zentren in einem der Quadrate Q1, . . . , Qq (der Seitenlange jeweils ≤ k)liegen fur ein Qj mit j 6= i mod (n + 1), so konnen wir eine k

k+1 -Naherung an einMIS fur solch einen Streifen erhalten. 2

Literatur:

• H. B. Hunt, M. V. Marathe, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz,R. E. Stearns: A unified approach to approximation schemes for NP- andPSPACE-hard problems for geometric graphs. In: Algorithms ESA’94, LNCS855 (1994), 424-435.

• Hochbaum/Maass: Approximation schemes for covering and packing pro-blems in image processing and VLSI. In: J. ACM 32 (1985), 130-136.

12.4 APX versus PTAS

Es stellt sich naturlich die Frage, ob die triviale Inklusion PTAS ⊆ APX echt istoder nicht. Der folgende Satz beantwortet diese Frage mit einer in der Komple-xitatstheorie ublichen Relativierung.


Satz 12.9 Gilt P 6= NP, so PTAS ( APX.

Beweis: Wir zeigen, dass —voraussgesetzt P 6= NP— kein r-approximativer furdas in Kapitel 5 als zu APX gehorig gezeigte Bin-Packing-Problem existiert furr ≤ 3/2− ε fur jedes ε > 0.Betrachte dazu folgende NP-vollstandige Entscheidungsproblemvariante fur das so-eben behandelte Partitionsproblem PARTITION.

Ggb: Gegenstande X = {x1, . . . , xn} mit Gewichten ai ∈ NGefragt: Gibt es eine Bipartition (Y1, Y2) von X mit∑

xj∈Y1

aj =∑

xj∈Y2

aj ?

Wir zeigen, wie man PARTITION in Polynomzeit losen konnte, wenn es fur Bin-Packing eine r-Approximation mit r ≤ 3/2 − ε gabe. Sei also (X, a) eine Instanzvon Partition B :=

∑x∈X a(x). Wir definieren nun die ”zugehorige“ Instanz von

Bin-Packing:Jedem Gegenstand xi ∈ X mit Gewicht ai ordnen wir einen Gegenstand x′i derGroße a′i = 2ai

B zu. Dabei konnen wir ai ≤ B/2 voraussetzen, da wir sonst trivia-lerweise eine unlosbare Instanz von PARTITION vorzuliegen hatten.; Instanz (X, a′) von Bin-Packing. Ist nun (X, a) eine positive Instanz von PAR-TITION, so ist m∗(X, a′) = 2 fur das zugehorige Bin-Packing-Problem. Ist aber(X, a) eine negative Instanz von PARTITION, so wird in jedem Fall ein dritterBehalter fur (X, a′) benotigt. Daraus ergibt sich die Behauptung, denn die angege-bene Reduktion ist Polynomzeit berechenbar. 2

Storend an den bisher in diesem Kapitel vorgestellten Approximationsschematamag sein, dass die Laufzeit der Algorithmen exponentiell von der angestrebtenGute der Approximation abhangt —man moge dies uberprufen! Wir stellen jetzteinen ”schoneren“ PTAS-Begriff vor.

Definition 12.10 Es sei P ∈ NPO. Ein Algorithmus A heißt volles Polynomzeit-Approximations-Schema (engl. fully PTAS, kurz FPTAS), falls A fur jedes Paarvon Eingaben (x, r), x eine Instanz von P und r > 1, eine r-approximative Losungzuruck liefert in einer Zeit, die polynomiell in |x| und in 1

r−1 ist.Die zugehorige Problemklasse nennen wir FPTAS.

In Abschnitt 4.1 haben wir bereits ein (einfaches) Beispiel fur ein Problem ausFPTAS kennen gelernt, namlich das Rucksackproblem. Tatsachlich gibt es nurverhaltnismaßig wenige (naturliche) Probleme in FPTAS; die meisten von ihnensind Verwandte des Rucksackproblems.Der Grund scheint darin zu liegen, dass man von einer ganzen Reihe von NPO-Problemen leicht nachweisen kann, dass sie nicht zu FPTAS gehoren.

Definition 12.11 Ein Optimierungsproblem heißt polynomiell beschrankt, wennes ein Polynom p gibt derart, dass —fur jede Instanz x ∈ IP und jede zulassigeLosung y ∈ SP(x)— m(x, y) ≤ p(|x|) gilt.


Satz 12.12 Gilt P 6= NP, so gehort kein NP-hartes polynomiell beschranktes Op-timierungsproblem zu FPTAS.

Beweis: Angenommen, es gibt ein FPTAS A fur das Maximierungsproblem P,dessen Laufzeit durch q(|x|, 1

r−1 ) fur ein Polynom q beschrankt ist (fur jede Instanzx und jedes r > 1). Da P polynomiell beschrankt ist, gibt es ein Polynom p mitm∗(x) ≤ p(|x|)[∗] fur jede Instanz x. Wir zeigen: fur r = 1 + 1

p(|x|) liefert A(x, r)eine optimale Losung fur x (in Polynomzeit q(|x|, p(|x|)):

Da m(x,A(x, r)) r-Approximation ist, gilt:

m(x,A(x, r)) ≥ m∗(x)p(|x|)

p(|x|) + 1= m∗(x)− m∗(x)

p(|x|) + 1[∗]> m∗(x)− 1

Da m(x,A(x, r)),m∗(x) ∈ N und m∗(x) großtmoglich, folgt

m∗(x) = m(x,A(x, r)).

Aus der NP-Harte von P folgt nun die Behauptung. 2

12.5 NP-Harte und Pseudo-Polynomialitat

Eine gewisse Sonderrolle spielen Optimierungsprobleme, deren Schwierigkeit vonder gewahlten Codierung der (ganzen) Zahlen (unar oder binar) abhangt.Ist x eine Instanz eines NPO-Problems, so bezeichne max(x) den Betrag der betrags-maßig großten vorkommenden Zahl.

Definition 12.13 Ein NPO-Problem P heißt pseudo-polynomiell, wenn es eineAlgorithmus A zu Losung von P gibt, der, fur jede Instanz x, mit einer Laufzeitarbeitet, die durch ein Polynom in |x| und max(x) beschrankt ist.

Beispiel 12.14 Das Rucksackproblem ist pseudo-polynomiell, siehe Satz 8.1. Fureine Instanz x = (X = {x1, . . . , xn}, {p1, . . . , pn}, {a1, . . . , an}, b) wurde max(x) =max(p1, . . . , pn, a1, . . . , an, b) sein.Fur die Laufzeit des Algorithmus von Kapitel 8 ist zu beachten:

O

(n

n∑i=1

pi

)⊆ O

(n2pmax

)⊆ O

(|x|2 max(x)

).

Satz 12.15 Es sei P ∈ FPTAS fur P. Gibt es ein Polynom p, sodass fur alleInstanzen x ∈ IP gilt:

m∗(x) ≤ p(|x|,max(x)),

so ist P pseudo-polynomiell.


Beweis: Es sei A ein FPTAS fur P. Betrachte

A′(x) = A(

x, 1 +1

p(|x|,max(x)) + 1

).

Aufgrund der Ganzzahligkeit der Losungen liefert A′(x) ein Optimum. Ist die Lauf-zeit von A(x, r) durch q

(|x|, 1

r−1

)beschrankt, so ist die Laufzeit von A(x) durch

q(|x|, p(|x|,max(x)) + 1) beschrankt, d.h. P ist pseudo-polynomiell. 2

Definition 12.16 Es sei P ein NPO-Problem und p ein Polynom. Pmax,p bezeich-ne die Einschrankung von P auf Instanzen x mit max(x) ≤ p(|x|). P heißt starkNP-hart, wenn es ein Polynom p gibt, sodass Pmax,p NP-hart ist.

Satz 12.17 Ist P 6= NP, so ist kein stark NP-hartes Problem pseudo-polynomiell.

Beweis: Angenommen, P ist ein stark NP-hartes Problem, das auch pseudo-poly-nomiell ist. Dann gibt es einen Algorithmus A, der P in der Zeit q(|x|,max(x)) lostfur ein geeignetes Polynom q und jede Instanz x ∈ IP . Fur jedes Polynom p kannPmax,p daher in Zeit q(|x|, p(|x|)) gelost werden. Da P stark NP-hart ist, musstefur ein p jedoch Pmax,p NP-hart sein, woraus P = NP folgt. 2.

Folgerung 12.18 Ist P ein stark NP-hartes NPO-Problem und gibt es ein Poly-nom p, sodass m∗(x) ≤ p(|x|,max(x)) fur jede Instanz x ∈ IP , so gilt P /∈ FPTAS,wenn nicht P = NP. 2

Die Satze aus diesem Abschnitt gestatten es, fur ein Problem zu schließen, dass es(unter gewissen komplexitatstheoretischen Annahmen) kein FPTAS besitzt. Dazudient auch der folgende Zusammenhang, fur dessen genaueres Verstandnis wir aufdie Vorlesung uber parametrisierte Algorithmen verweisen.

Mitteilung 12.19 Besitzt das einem Optimierungsproblem P entsprechende pa-rametrisierte Entscheidungsproblem keinen Festparameteralgorithmus, so liegt Pnicht in FPTAS.

13 ZWISCHEN APX UND NPO 95

13 Zwischen APX und NPO

Wie wir in Kapitel 11 gesehen hatten, gibt es Probleme (wie das Handelsreisenden-problem), die sich (vorbehaltlich P 6= NP) nicht bis auf einen konstanten Faktormit einem Polynomzeitalgorithmus angenahert losen lassen.In solchen Fallen stellt sich die Frage, ob es denn wenigstens moglich ist, Leistungs-garantien fur Approximationsalgorithmen zu finden, die von der Lange der Instanzabhangen.In diesem Abschnitt lernen wir Beispiele fur solche Naherungsalgorithmen kennen.Betrachten wir zunachst eine weitere Verallgemeinerung des uns nun schon wohl-bekannten Knotenuberdeckungsproblems:

13.1 Das Mengenuberdeckungsproblem (Set Cover, SC)

I : Eine Kollektion C von Teilmengen einer endlichen Grundmenge S.S : Eine Mengenuberdeckung C ′ ⊆ C fur S, d.h. eine Teilkollektion,

sodass jedes Element der Grundmenge S zu wenigstens einem Elementder Teilkollektion gehort.

m : |C ′|opt : min

Zusammenhang mit Knotenuberdeckung Das Knotenuberdeckungspro-blem ist insofern ein Mengenuberdeckungsproblem, als dass dort die Grundmen-genelemente ”Kanten“ heißen und ein Element der Kollektion einem ”Knoten“ ent-spricht, genauer der Menge von Kanten, die mit namlichen Knoten inzidieren.Insofern ist der folgende Greedy-Algorithmus fur das Mengenuberdeckungsproblemeine unmittelbare Verallgemeinerung eines Greedy-Algorithmus des Knotenuber-deckungsproblems, denn die Auswahl eines Elementes der Kollektion mit großterMachtigkeit entspricht gerade der Wahl eines Knotens von großtem Grad.In ahnlicher Weise lasst sich auch das Hitting-Set-Problem als Spezialfall des Men-genuberdeckungsproblems auffassen (und umgekehrt).

GreedySC (S, C)

0. Teste, ob⋃

c∈C c = S gilt.

1. U := S

2. Fur jede Menge ci ∈ C setze c′i := ci;

3. C ′ := ∅;

4. Solange U 6= ∅ tue:

4a. Wahle unter den c′i eine Menge c′j großter Machtigkeit

4b. C ′ := C ′ ∪{c∗j};

4c. U := U \ c′j ;

4d. Fur jede Menge c′i setze c′i := c′i − c′j .


5. Liefere C ′ zuruck.

Satz 13.1 Ist n = |S|, so ist GreedySC ein (blnnc+ 1)-approximativer Polynom-zeitalgorithmus fur das Mengenuberdeckungsproblem.

Beweis: Starten wir zunachst mit einem kleinen mathematischen

Exkurs

H(r) :=∑r

i=11i bezeichnet die r-te harmonische Zahl. Die Folge (H(r)) konver-

giert nicht, wachst aber recht langsam, genauer gesagt wie der naturliche Logarith-mus. Noch genauer gilt (siehe Graham/Knuth/Patashnik: Concrete Mathematics,Addison-Wesley, 1989):

bln rc ≤ H(r) ≤ bln rc+ 1

Um die Aussage des Satzes zu beweisen, werden wir zeigen:∑ci∈C∗

H (|ci|) ≥ |C ′| (∗)

Dabei ist C∗ irgendeine optimale Uberdeckung und C ′ eine GreedyVC gelieferteLosung. Wegen |ci| ≤ n folgt aus (∗):

|C ′| ≤∑

ci∈C∗

H (|ci|) ≤∑

ci∈C∗

H(n) ≤ |C∗|H(n) ≤ |C∗| (blnnc+ 1) ,

was die Satzbehauptung liefert. (Die Polynomzeitbehauptung ist trivial.)

Um (∗) nachweisen zu konnen, fuhren wir noch einige Bezeichnungen ein:

Ist x =

S,

=C︷︸︸︷{c1, . . . , cm}

eine SC-Instanz, so sei a1, . . . , a|C′| die Folge der Indizes

derjenigen Teilmengen aus der Kollektion, die zu C ′ ⊆ C gehoren, d.h.

C ′ ={

ca1 , . . . ca|C′|

}.

Fur jedes j ∈ {1, . . . , |C ′|} , i ∈ {1, . . . ,m} sei cji der ”uberlebende“ Teil von ci,

bevor die Teilmenge caj gewahlt worden ist durch GreedySC.Damit ist c1

i = ci (fur alle i ∈ {1, . . . ,m}).Außerdem vereinbaren wir: c

|C′|+1i = ∅ fur alle i ∈ {1, . . . ,m}. Die Menge der

Elemente von ci, die das erste Mal durch caj uberdeckt werden, ist

ci ∩ cjaj

= cji ∩ cj

aj= cj

i \ cj+1i . [+]


li sei der großte Index, fur den clii 6= ∅ gilt, d.h. cli+1

i = ∅, m.a.W., nachdem calizur

Uberdeckungs-Kollektion hinzugefugt wurde, sind alle Elemente von ci abgedeckt.

Mit diesen Bezeichnugsweisen zeigen wir zwei Behauptungen:

Behauptung 1:

∀i ∈ {1, . . . ,m} : H (|ci|) ≥|C′|∑j=1

∣∣∣ci ∩ cjaj

∣∣∣∣∣∣cjaj

∣∣∣Behauptung 2: ∀C ′′ ⊆ C,C ′′ ist Mengenuberdeckung

∑ci∈C′′

|C′|∑j=1



∣∣∣ ≥ |C ′|

Aus beiden Behauptungen folgt sofort (∗), denn Behauptung 2 gilt insbesonderefur C ′′ = C∗, also ist

|C ′| ≤∑

ci∈C∗

|C′|∑j=1



∣∣∣ ≤∑

ci∈C∗

H (|ci|).

Beide Behauptungen ergeben sich nun nach einigen leichten algebraischen Manipu-lationen.Zu Behauptung 1: Es sei i ∈ {1, . . . ,m}. Da GreedySC fur jedes 1 ≤ j ≤ |C ′|stets eine großte uberlebende Menge wahlt, gilt

[$]∣∣∣cj

i

∣∣∣ ≤ ∣∣∣cjaj

∣∣∣in unserer Notation.


Also ist:

|C′|∑j=1



∣∣∣ [+]=

C′∑j=1

∣∣∣cji

∣∣∣− ∣∣∣cj+1i


∣∣∣[$]

≤|C′|∑j=1

∣∣∣cji

∣∣∣− ∣∣∣cj+1i

∣∣∣∣∣∣cji

∣∣∣Def. li≤

li∑j=1

|cji |∑

K=|cj+1i |+1

1|cj

i |

[]]

≤li∑

j=1

|cji |−|c

j+1i |∑

k=1

1k + |cj+1

i |

|cj+1i |≥0

≤li∑

j=1

|cji |−|c

j+1i |∑

k=1

1k

=li∑

j=1

(H(∣∣∣cj

i

∣∣∣)−H(∣∣∣cj+1

i

∣∣∣))Teleskop

= H(∣∣c1

i

∣∣)−H(∣∣∣cli+1

i

∣∣∣)s. o.= H (|ci|)

Die Ungleichung []] ist trivial, denn sie bedeutet:

∀k = 1, . . . , |cji | − |c

j+1i | : |cj

i | ≥ k + |cj+1i |.

Zu Behauptung 2:

∑ci∈C′′

|C′|∑j=1

∣∣∣ci ∩ ciaj


∣∣∣ =|C′|∑j=1

1∣∣∣cjaj

∣∣∣∑

ci∈C′′


∣∣∣C′′ Uberdeckung!

≥|C′|∑j=1

1∣∣∣cjaj

∣∣∣ ·∣∣∣cj

aj

∣∣∣ = |C ′|

Beim letzten ≥ ist 6= moglich, falls gewisse Elemente mehrfach abgedeckt werden.2

Bemerkung 13.2 Die in Satz 13.1 angegebene Abschatzung der Leistungsgute vonGreedySC ist nicht verbesserbar. Es gibt eine Folge von Instanzen, fur die dieSchranke auch erreicht wird.

Bemerkung 13.3 GreedySC ist optimal in dem Sinne, dass es (unter einigen

”wahrscheinlich“ komplexitatstheoretischen Annahmen) fur kein ε > 0 einen ”(ln−ε)-Approximationsalgorithmus“ fur SC gibt.


Betrachten wir jetzt noch ein weiteres Problem ”jenseits von APX“:

13.2 Graphenfarben

Schon weiter oben haben wir diskutiert, wie man Algorithmen zum Auffinden vonunabhangigen Mengen in Graphen ”gebrauchen“ kann, um Algorithmen zum Gra-phenfarben zu erhalten. Auf dieser Idee fußt auch folgendes Verfahren.

GreddyGC (G=(V,E))

1. i := 0; U := V

2. Solange U 6= ∅ tue:

2a. i := i + 1;2b. I := GreedyIndependentSet(G(U));2c. Farbe Knoten aus I mit ”Farbe“ i;2d. U := U \ I

3. Liefere so erhaltene Farbung f : V → N zuruck.

Lemma 13.4 Ist G = (V,E) k-farbbar, so benotigt GreedyGC hochstens 3|V |logk(|V |)

viele Farben zum Farben von G.

Beweis: Es sei H = G(U) irgendein im Schritt 2b. verarbeiteter Teilgraph von G.Da G k-farbbar ist, ist auch H k-farbbar. Zum Fortgang des Beweises brauchen wirfolgenden

Hilfsatz 13.5 Wird ein Graph H GreedyIndependentSet als Eingabe gegeben, sowird eine unabhangige Menge I ⊆ U geliefert, die wenigstens dlogk (|U |)e vieleKnoten enthalt.

Beweis des Hilfsatzes: Da H k-farbbar, enthalt H eine unabhangige Menge Imit wenigstens |U | /k Knoten. Jeder Knoten dieser Menge hat einen Maximalgrad(|U | − |U | /k) (denn sonst gabe es Verbindungen zwischen Knoten I). Damit isttrivialerweise der Minimalgrad in H maximal (|U | − |U | /k) . Da als erster Knotenv1 (fur I) von GreedyIndependentSet einer minimalen Grades gewahlt wird under samt seinen hochstens (|U | − |U | /k) vielen Nachbarn entfernt wird, wird dernachste Knoten v2 in H (U \N [v1]) gesucht mit

|U \N [v1]| > |U | − (|U | /k + 1) = |U | /k − 1.

Da H (U \N [v1]) k-farbbar, lasst sich das Argument wiederholen.Abgebrochen wird diese Suche, wenn U erschopft ist.Dazu sind mindestens dlogk (|U |)e viele Schritte notig, und soviele Knoten werdenauch wenigstens zu I hinzugenommen. 2

Wegen des Hilfsatzes werden wenigstens dlogk (|U |)e viele Knoten mit Farbe igefarbt. Wie groß ist U vor dem Durchlaufen der Schritte 2a.-2d.?


Fall 1: Solange |U | ≥ |V |/ logk(|V |), gilt wegen |V |/ logk(|V |) >√|V |:

dlogk |U |e ≥ logk |U | ≥ logk (|V | / logk (|V |)) > logk

√|V | = 1

2logk (|V |)

Da U bei jedem Durchlauf der Schleife ”2“ um wenigstens 12 logk (|V |) ab-

nimmt, kommt der Fall 1 hochstens 2 |V | / logk (|V |) oft zur Anwendung, unddabei werden hochstens 2 |V | / logk (|V |) viele Farben benutzt.

Fall 2: Sobald |U | < |V |/ logk(|V |), reichen trivialerweise |V |/ logk(|V |) viele Far-ben aus.

Fall 1 und Fall 2 zusammen liefern die Behauptung des Lemmas. 2

Satz 13.6 Ist n = |V |, so ist GreedyGC ein O(n/ log(n))-approximativer Algorith-mus furs Graphenfarben.

Beweis: Nach dem Lemma benotiget GreedyGC hochstens 3n/ logk(n) viele Farbenmit k = m∗(G). Also ist

m(G, GreedyGC(G))m∗(G)

≤ 3n log(m∗(G)/ log(n)m∗(G)

≤ 3n

log(n).

2

Bemerkung 13.7 Der soeben dargestellte O(n/ log n)-approximative Algorithmusist nicht bestmoglich. So wurde ein O

(n (log log n)2

(log n)3

)-approximativer Algorithmus ge-

funden. Auf der anderen Seite ist bekannt, dass es —sofern nicht P = NP— keinenn1/7−ε-approximativen Algorithmus geben kann fur jedes ε > 0. Insbesondere durftedas Graphenfarbeproblem nicht in APX liegen.

14 ZWISCHEN PTAS UND APX 101

14 Zwischen PTAS und APX

Wir stellen hier eine Verallgemeinerung der Klasse PTAS vor, bei der die Naherungs-gute mit wachsendem Wert einer optimalen Losung sich verbessern kann, die vor-gegebene Schranke r also nur einen asymptotischen Sinn erfullt.

Definition 14.1 Ein NPO-Problem P liegt in PTAS∞, in Worten: P hat einasymptotisches Approximationsschema, wenn es einen Algorithmus A gibt und ei-ne Konstante k, sodass —fur jede Instanz x von P und fur jede rationale Zahlr ≥ 1— A(x, r) in Polynomzeit eine Losung liefert, deren Leistungsfaktor hochstensr + k

m∗(x) betragt.

Naturlich gilt: PTAS ⊆ PTAS∞ ⊆ APX. (∗)

Mitteilung 14.2 Unter der Annahme P 6= NP sind beide Inklusionen in (∗) echt.

Wir werden hier zwei Probleme aus PTAS∞ betrachten: das Kantenfarben in einemGraphen sowie Bin-Packing. Wir haben in Kapitel 12 gesehen, dass Bin-Packingnicht in PTAS liegt, sofern P 6= NP. Damit hatten wir den ersten Teil der Mittei-lung 14.2 am Ende dieses Kapitels sogar bewiesen.

14.1 Kantenfarben

I : Graph G = (V,E)S : Eine Farbung der Kanten, d.h. eine Partition von E in E1, . . . , EK ,

sodass fur jedes 1 ≤ i ≤ K gilt: Keine zwei Kanten aus Ei haben einengemeinsamen Endpunkt

m : Anzahl der Farben, d. h. also K.opt : min.

Satz 14.3 (Vizing) Es gibt einen Polynomzeitalgorithmus, welcher bei Eingabe ei-nes Graphen G mit Maximalgrad ∆ eine Kantenfarbung mit hochstens ∆+1 vielenFarben liefert.

Beweis: Ist G = (V,E) der Eingabegraph vom Maximalgrad ∆, so farbt A G, in-demA nacheinander die Kanten von E farbt, wobei evtl. ”fruhere“ Kantenfarbungenspater revidiert werden. A arbeitet im Grunde wie folgt:

1. E′ := E;E := ∅;

2. Solange E′ 6= ∅, tue:

2a) Wahle Kante {u, v} ∈ E′.

2b) Erweitere die Kantenfarbung von E auf E ∪ {{u, v}}, sodass(V,E ∪ {{u, v}}

)mit hochstens ∆ + 1 vielen Farben gefarbt ist.


2c) E′ := E′ \ {{u, v}} ;E := E ∪ {{u, v}}

Naturlich mussen wir 2b) jetzt noch prazisieren. Als Farbmenge nehmen wir F ={1, . . . ,∆ + 1}. Eine Farbung ist eine Abbildung f : E → F . Wir gehen davon aus,dass fur (V ;E) eine Kantenfarbung mit hochstens ∆ + 1 vielen Farben konstru-iert wurde. (Formal fuhren wir also einen Induktionsbeweis uber

∣∣E∣∣ mit trivialenInduktionsanfang fur E = ∅.) f ist also partiell und vorlaufig auf E festgelegt.

Wir fuhren folgende Notation ein:

• Ist v ∈ V beliebig, so bezeichne

C(v) ={

f ∈ F | ¬∃u ∈ V : {u, v} ∈ E ∧ f ({u, v}) = f}

die Farbmenge, die fur ”weitere Kanten“, die mit v inzidieren, noch ”frei“ ist.

• Da δ(v) ≤ ∆, ist fur alle v ∈ V die Menge C(v) 6= ∅. Daher gibt es eineReprasentantenfunktion c : V → F mit ∀v ∈ V : c(v) ∈ C(v).

Es sei jetzt (und im Folgenden) {u, v} die in Schritt 2a) gewahlte Kante. Wir be-trachten jetzt sogenannte Kantenfarbfolgen, das sind mit u inzidierende 11 Knoten-folgen x0, . . . , xs mit x0 = v und f({u, xi}) = c(xi−1). Eine Kantenfarbfolge heißtmaximal, wenn es keine weitere Kanten {u, x} in E gibt (mit x /∈ {x0, . . . , xs}) mitf({u, x}) = c(xs).

Hilfsatz 14.4 Ist x0, . . . , xs eine Kantenfarbfolge mit c(xs) ∈ C(u), so ist f zueiner Farbung auf E ∪ {{u, v}} erweiterbar.

Beweis: Setze einfach f({u, xi}) := x(xi) fur 0 ≤ i ≤ s und lasse sonst die alteFarbung bestehen. 2

Die Situation vor (links) und nach (rechts) dem Umfarben mit dem Hilfssatz, s = 4:

0

x1

x2

x3

x4

c(x )

x =v

c(x )0

1

c(x )2

c(x )3

0

x1

x2

x3

x4

x =v

1

2

c(x )3

c(x )4

c(x )

c(x )

c(x )0

u

11Inzidenz bzgl. E ∪ {{u, v}}


In Polynomzeit kann nun eine maximale Kantenfarbfolge (an u) gefunden werden.Wegen dem Hilfsatz konnen wir c(xs) /∈ C(u) annehmen.Wegen der Maximalitat der Folge gibt es ein 0 ≤ i ≤ s mit f({u, xi}) = c(xs), dennc(xs) ist ja nicht mehr ”frei“ zum Farben von u-inzidenten Kanten.

Damit gilt:c(xi−1) = c(xs).

Betrachte nun einen langsten Pfad pi−1 in (V,E), der bei xi−1 startet und dessenKanten abwechselnd mit c(u) und c(xs) gefarbt sind. Es bezeichne w den letztenKnoten dieser Folge. Wir unterscheiden zwei Falle:

(a) w 6= u. Dann konnen wir alle ursprunglich mit c(u) gefarbten Kanten mit c(xs)farben und umgekehrt. Weiter farben wir nun Kante {u, xi−1} mit c(u). Furdiese erhaltene Kantenfarbfolge x0, . . . , xi−1 ist der Hilfsatz anwendbar.

(b) w = u. Jetzt suchen wir in Linearzeit einem weiteren langsten Pfad ps, der beixs startet und dessen Kanten abwechselnd mit c(u) und c(xs) gefarbt sind.Angenommen ps wurde pi−1 irgendwo ”schneiden“, so kann dies nicht ”mit-tendrin geschehen“, da so an einem Knoten zwei verschiedene mit c(u) oderc(xs) gefarbte Kanten anstoßen. Ware aber der letzte Knoten von ps gleichu, so stoßen an u zwei Kanten mit der selben Farbe c(xs).Also konnen wir ps analog zu (a) umfarben und dann den Hilfsatz anwenden.2

Folgerung 14.5 Minimales Kantenfarben gehort zu PTAS∞. 2

Beweis: Da ∆(G) ≤ m∗(G), gilt fur die Lsung m(G) unseres Algorithmus m(G) ≤∆(G) + 1 ≤ m∗(G) + 1. Daher ist:

m(G)m∗(G)

≤ m∗(G) + 1m∗(G)

= 1 +1

m∗(G).

2

Mitteilung 14.6 Mit Hilfe der Gap-Technik lasst sich zeigen, dass das Kanten-farbeproblem kein PTAS besitzt, sofern nicht P = NP.

14.2 Bin Packing (BP)

Der Schlussel fur die Entwicklung eines PTAS∞ fur BinPacking liegt in der po-lynomiellen Losbarkeit der folgenden eingeschrankten Variante: Minimum (c, δ)eingeschranktes BP (fur c ∈ N, c > 0 und δ ∈ Q, δ ≤ 1) ist gegeben, falls eshochstens c unterschiedliche Großen der Gegenstande gibt und jeder Gegenstandwenigstens δ groß ist (also einen Bruchteil der mit 1 angenommenen Kapazitat je-des Behalters).Um Bruchzahlen zu vermeiden bei Angabe der Gegenstandsgroßen si, gestattenwir noch die Angabe der Behaltnisgroße B, weichen also formal von unserer Ur-sprungsdefinition von BinPacking leicht ab. In diesem Sinne ware (I = {3 : 4, 5 :2, 7 : 1}, B = 8) eine Instanz von Minimum (3, 3/8)-eingeschranktem BP.


Lemma 14.7 Minimum (c, δ)-eingeschranktem BP kann in der Zeit O (nq) gelostwerden, wobei n die Zahl der Gegenstande in der Eingabeinstanz ist und q nur vonc und δ, nicht aber von n abhangt.

Beweis: Es sei (I,B) eine Instanz von Min.(c, δ)-eingeschranktem BP. Der Typeines Behalters ist ein c-dimensionaler Vektor ~b = (t1, . . . , tc) von naturlichen Zah-len mit 0 ≤ ti ≤ ni, sodass

∑ci=1 tisi ≥ B.

Fur jeden Typ gilt wegen δB ≤ si:

c∑i=1

ti ≤ 1δB

∑tisi ≤

1δ

Erinnerung

∣∣∣{(x1, . . . , xs) | xi ∈ N, xi ≥ 0,∑

xi ≤ m}∣∣∣ = ( m + s

m

)=(

m + ss

)Anwendung: Es gibt hochstens q =

(c +

⌊1δ

⌋c

)viele Typen von Behaltern.

Eine zulassige Losung von Minimum (c, δ)-eingeschranktem BP kann daher durcheinen q-dimensionalen Vektor ~y = (y1, . . . , yq) beschrieben werden, wobei yi ≥0 angibt, wie viele Behalter von Typ i in der Losung vorkommen. Da trivialerWeise hochstens n Behalter verwendet werden mussen, gibt es daher hochstens nq

verschiedene zulassige Losungen. In diesem Raum kann in der Zeit O(nq) nach eineroptimalen Losung gesucht werden.

2

Das PTAS∞ fur Bin-Packing lasst sich wie folgt skizzieren:

1. Entferne ”kleine Gegenstande“.

2. Gruppiere die verbleibenden Gegenstande in eine konstante Zahl von Großen-klassen.

3. Finde optimale Losung fur verbleibende Instanz (wie eben).

4. Mache die Gruppierung aus Schritt 2 ruckgangig.

5. Fuge die ”kleinen Gegenstande“ wieder ein.

Ein Verfahren fur den dritten Schritt haben wir soeben kennen gelernt. Schritt 1dient im wesentlichen dazu, die erforderliche δ-Schranke zu bekommen, und Schritt2 dient dazu, die Zahl der verschiedenen vorkommenden Großen zu beschranken.

Zum Gruppieren der Gegenstande

Es sei x eine Bin-Packing-Instanz. Die Gegenstande x1, . . . , xn seien der Große nachabsteigend sortiert. Fur jede naturliche Zahl k ≤ n sei m := bn/kc . Teile die n


Gegenstande auf m(+1) Gruppen Gi auf mit Gi = {x(i−1)k+1, . . . , xik}, 1 ≤ i ≤ mund Gm+1 = {xmk+1, . . . , xn}.Wir definieren nun eine neue Instanz xk

g von BP (mit der selben Behaltergroße),sodass xk

g fur jeden Gegenstand xj von der ursprunglichen Instanz, der aus Gi

war, einen Gegenstand der Große s(x(i−1)k+1) enthalt fur i = 2, . . . ,m + 1. Es gibtalso hochstens mk Gegenstande in xk

g , und diese Gegenstande haben hochstens mverschiedene Großen. Wir ignorieren die k großten Gegenstande auf diese Weise.

Lemma 14.8 m∗(xkg) ≤ m∗(x) ≤ m∗(xk

g) + k.

Beweis: Jede Losung fur xkg ist trivialerweise eine fur x, wenn wir weiter k Behalter

fur die ersten (großten) Gegenstande von x bereithalten.Eine Losung von x wiederum kann wie folgt in eine fur xk

g umgebildet werden: (a)Entferne alle Gegenstande aus der letzten Gruppe, (b) ersetze jeden Gegenstandaus Gi durch einen Gegenstand, der so groß ist wie xik+1 (wenn notig; Gm+1 hatevtl. weniger Elemente als Gm). 2

Zur Behandlung”kleiner Gegenstande“

Es sei x eine BP-Instanz. Fur jedes δ ∈ Q, δ ∈(0, 1

2

], sei xδ die Instanz, die aus

x durch Fortlassen aller Gegenstande, die kleiner als δB sind, entsteht. Haben wirnun eine Losung fur xδ, die M Behalter benotigt, so benutzen wir FirstFit, um diekleinen Gegenstande wieder einzufugen.

Lemma 14.9 Auf diese Weise lasst sich in Polynomzeit eine Losung fur x finden,die hochstens max(M, (1 + 2δ)m∗(x) + 1) viele Behalter benutzt.

Beweis: Wir unterscheiden zwei Falle:

(a) Es wurden keine neuen Behalter durch FirstFit geoffnet→M Behalter reichen.

(b) Es wurden M ′ ≥ 1 neue Behalter durch FirstFit geoffnet. Wie schon in Kapi-tel 5 uberlegt, enthalten alle Behalter (mit moglicher Ausnahme des zuletztgeoffneten) hochstens δB vielen freien Platz. Daher ist

(1− δ) (M + M ′ − 1)︸︷︷︸# Behalter bis auf den letzten

≤∑n

i=1 s(xi)B

≤ m∗(x)

; M + M ′ ≤ 11− δ

m∗(x) + 1 ≤ (1 + 2δ)m∗(x) + 1

denn wegen δ ∈(0, 1

2

]gilt 2δ2 ≤ δ, also 1 ≤ 1− 2δ2 + δ. 2


14.3 EIN PTAS∞ fur BP

AsymptBP(x,B, r)

1. Falls r ≥ 2 nimm NextFit (oder FirstFit) (s. Kapitel 5).

2. δ := (r − 1)/2;

3. Sei xδ die aus x durch Fortlassen von Gegenstanden der Große < δB entste-hende Instanz; n′ sei die Zahl der Gegenstande in xδ.

4. k :=⌈(r − 1)2n′/2

⌉;

5. Sei xkδ,g die aus xδ durch Gruppierung gebildete Instanz.

6. Finde optimale Losung xkδ,g vom Wert m∗(xk

δ,g).

7. Fuge die ersten (großten) k Gegenstande von xδ in k ”neue“ Behalter.

8. Wende FirstFit an, um die ”kleineren Gegenstande“ wieder einzufugen.

9. Liefere die so erhaltene Packungsvorschrift zuruck.

Satz 14.10 AsymptBP ist ein PTAS∞ fur BP.

Beweis: AsymptBP lauft in Polynomzeit, da eine optimale Losung fur xkδ,g in Zeit

nq gefunden werden kann mit q = f(dn′/ke , δ), siehe Lemma 14.7. Beachte: dn′/kehangt nicht von n ab, nur von r (bzw. δ).Wegen Lemma 14.8 ist der Wert einer Losung von AsymptBP beschrankt durchm∗(xk

δ,g) + k. Alle Gegenstande in xδ haben eine Große von wenigstens δB, sodassδn′ ≤ m∗(xδ) folgt, und damit

k ≤ (r − 1)2

2n′ + 1 = (r − 1)δn′ + 1 ≤ (r − 1)m∗(xδ) + 1.

Mit Lemma 14.8 folgt m∗(xkδ,g) + k ≤ m∗(xδ) + (r − 1)m∗(xδ) + 1 = rm∗(xδ) + 1.

Benutzen wir r = (1 + 2δ) in Lemma 14.9, so erhalten wir, dass maximal

max(rm∗(xδ) + 1, rm∗(x) + 1) ≤ rm∗(x) + 1

viele Behalter von AsymptBP benutzt werden. 2

Man kann sogar zeigen:

Mitteilung 14.11 BinPacking liegt in FPTAS∞.

15 APPROXIMATIONSKLASSEN UND REDUKTIONEN 107

15 Approximationsklassen und Reduktionen

15.1 Erinnerung: Reduktion fur P versus NP

In Kapitel 3 hatten wir den allgemeinen Begriff einer Turing-Reduktion (mit Po-lynomzeitbeschrankung) kennen gelernt. Aus der Grundvorlesung in TheoretischerInformatik durfte ein abgeschwachter Begriff noch eher bekannt sein:

Definition 15.1 Ein Entscheidungsproblem P1 heißt Karp-reduzierbar (oder many-one-reduzierbar) auf ein Entscheidungsproblem P2, wenn es einem (Polynomzeit-)Algorithmus R gibt, der eine Instanz x von P1 in eine Instanz y von P2 uberfuhrtin einer Weise, dass x eine Ja-Instanz von P1 ist und y eine Ja-Instanz von P2

ist.

Zentral fur die Entwicklung von P versus NP-Theorie ist es, Probleme zu kennen, diehart fur NP sind in dem Sinne, dass ein deterministischer Polynomzeitalgorithmusfur ein solches Problem die Existenz deterministischer Polynomzeitalgorithmen furalle NP-vollstandigen Probleme nach sich ziehen wurde. Wir wollen etwas Entspre-chendes auch im Falle der Optimierungsprobleme entwickeln, mussen uns aber ersteinmal an die wichtigsten Dinge aus der NP-Vollstandigkeitstheorie erinnern, dadie Verhaltnisse dort einfacher sind.

Das ”generische“ NP-vollstandige Problem ist das Folgende:

Ggb: nichtdeterministische Turing-Maschine, Eingabe x von TM, Polynom p

Frage: Akzeptiert TM das Wort x in hochstens p(|x|) Schritten?

Dieses Problem liegt in NP, und wurde es in P liegen, so ware P=NP.

Das vielleicht wichtigste NP-vollstandige Problem ist das Erfullbarkeitsproblem(SAT):

Ggb: KNF Formel F auf einer Menge V von Booleschen Variablen.

Frage: Ist F erfullbar? D.h., gibt es eine Variablenbelegung f : V → {true, false},die F ”wahr macht“?

Satz 15.2 Satz von Cook(-Levin) Das Erfullbarkeitsproblem ist NP-vollstandig.

Zum Beweis verweisen wir auf andere Vorlesungen.Die Beweisidee besteht in der formelmaßigen Darstellung des ”Rechenteppichs“ ei-ner Turing-Maschine.

Wir wollen den Karpschen Reduktionsbegriff an zwei Beispielen uben.


{0, 1}-Lineares Programmieren

Ggb: Menge von Variablen Z = {z1, . . . , zn}, die Werte aus {0, 1} annehmenkonnen; Menge I von linearen Ungleichungen (mit Variablen aus Z und ganzzahli-gen Koeffizienten).

Frage: Hat I eine Losung, d.h. irgendeine Variablenbelegung, die alle Ungleichun-gen erfullt?

Lemma 15.3 {0, 1}-lineares Programmieren ist NP-hart.

Beweis: Betrachte eine Instanz x = (V,F) von SAT mit V = {x1, . . . , xn}. Essei lj1 ∨ . . . ∨ ljnj

die j-te Klausel in F . Als entsprechende Ungleichung sehen wir%j1 + . . . + %jnj

≥ 1 an mit %jx = zi, falls ljk= xi, und %jk

= (1− zi), falls ljk= xi.

Dadurch ergibt sich eine {0, 1}-LP-Instanz y = (Z, I). Ist f : V → {true, false}eine Wahrheitsbelegung, so ist f(F) = true gdw. f ′ erfullt alle Ungleichungen in I,wobei f ′(zi) = 1 gdw. f(xi) = true. 2

3SAT

Wie SAT, nur dass jede Klausel (hochstens) drei Literale enthalt.

Lemma 15.4 3SAT ist NP-hart.

Beweis: Wir zeigen, wie allgemeine SAT-Formeln in (hinsichtlich der Erfull-barkeit) aquivalente 3SAT-Formeln uberfuhrt werden konnen. Ist lj1 ∨ . . .∨ ljnj

eineKlausel mit nj > 3, so kann durch Einfuhren von nj − 3 Variablen yj,1, . . . yj,n−3

und insgesamt nj − 2 Klauseln die 3SAT-Restriktion erfullt werden. Die Klauselnsehen dafur wie folgt aus:

(lj1 ∨ lj2 ∨yj1), (yj1 ∨ lj3 ∨yj2), . . . , (yj,nj−4∨ ljnj−2 ∨yj,nj−3), (yj,nj−3∨ ljnj−1 ∨ ljnj)

2

15.2 Die Welt von NPO-Problemen

Betrachten wir zunachst die folgende, den Begriff eines r-approximativen Algorith-mus nur verallgemeinernde Definition:

Definition 15.5 Ist P ein NPO-Problem, A ein Approximationsalgorithmus furP und r : N → (1,∞) eine Abbildung, so heißt A r(n)-Approximation, falls furjede Instanz x ∈ IP mit SP(x) 6= ∅ die Leistungsgute der zulassigen Losung A(x)der Ungleichung R(x,A) ≤ (|x|) genugt.


Das Verhalten des Algorithmus A ist bei Eingaben, die keine zulassige Losungenhaben, unbestimmt. Naturlich wird keine Losung zuruck geliefert.

Definition 15.6 Ist F eine Klasse von Funktionen f : N → (0,∞) so bezeichnetF-APX die Klasse der Probleme, fur die ein r(n)-approximativer Polynomzeitalgo-rithmus (fur ein r ∈ F) existiert.

Spezielle Funktionsklassen sind:

• LOG:= O(log(n))

• POLY:=⋃

k>0 O(nk)

• EXP:=⋃

k>0 O(2nk

)

Satz 15.7

PTAS ⊆ APX ⊆ LOG−APX ⊆ POLY−APX ⊆ EXP−APX ⊆ NPO.

Gilt vielleicht EXP−APX = NPO ?Ein verfuhrendes Argument ist das folgende:

Wegen der polynomiellen Schranke auf der Rechenzeit fur die Maßfunktion mP istdoch jedes NPO-Problem P h · 2nk

-approximierbar fur geeignete h und k.Es gibt eben Probleme, fur die bereits die Frage, ob eine zulassige Losung existiert,NP-hart ist. Dazu gibt es im Folgenden Beispiele.

Satz 15.8 Wenn P 6= NP, so EXP−APX 6= NPO.

Beweis: Betrachten wir das folgende NPO-Problem:Minimum {0, 1}-LP

I = A ∈ Zm×n, b ∈ Zm, w ∈ Nn

S : x ∈ {0, 1}n mit Ax ≥ bm :

∑wixi (Skalarprodukt von w und x)

opt : min.

Ware Minimum {0, 1} − LP ∈ EXP − APX, so konnten wir an dem Verhalteneiner Polynomzeit-Approximation fur eine Instanz x ablesen, ob die selbe Instanzx, aufgefasst als {0, 1}-LP-Instanz, eine JA-Instanz ist oder nicht. Die Behauptungfolgt mit Lemma 15.3. 2


15.3 AP-Reduzierbarkeit

Bei Entscheidungsproblemen genugte es, einen Reduktionsbegriff von P1 auf P2 sozu definieren, dass man P1 ”mit Hilfe von“ P2 losen kann, was beim KarpschenReduktionsbegriff bedeutet, dass Instanzen von P1 in Instanzen von P2 (in Poly-nomzeit) umgerechnet werden konnen. Dies genugt fur einen Approximationsreduk-tionsbegriff nicht; vielmehr benotigen wir einen weiteren Algorithmus, der Losungenvon P2 in solche fur P1 zuruckrechnet, und letztere Rechnung sollte naturlich (ineinem noch zu detaillierenden Sinne) die Naherungsgute bewahren.

Schematisch konnen wir uns eine solche Approximationsreduktion wie in Abb. 7vorstellen.

PS (f(x))

2

g

f

x

y

f(x)

g(x,y)

P1

S (x)

Abbildung 7: Schematische Approximationsreduktion

Approximationsguteerhaltung am Beispiel:Knotenuberdeckung ; MaxClique:

Ist G = (V,E) ein Graph, so ist der Komplementgraph Gc = (V,Ec) definiertdurch Ec = {{v1, v2} ⊆ V | v1 6= v2, {v1, v2} /∈ E}.

Lemma 15.9 V ′ ⊆ V ist Knotenuberdeckung in G gdw, V \ V ′ ist Clique in Gc.

Beweis: Angenommen V ′ ⊆ V ist Knotenuberdeckung. Gabe es eine ”Kante“{u, v} /∈ Ec, u, v ∈ V \ V ′, so ware {u, v} ∈ E und {u, v} ∩ V = ∅, also V ′ keineUberdeckung. Ist V \V ′ Clique, so betrachte eine Kante {u, v} mit {u, v}∩V ′ = ∅.Also ist {u, v} ∈ V \ V ′, d. h. {u, v} ∈ V \ V ′, d.h. {u, v} ∈ Ec. Kanten aus E sindalso durch V ′ abgedeckt. 2

Das Lemma 15.9 zeigt, dass das Knotenuberdeckungsproblem (Frage nach der Exi-stenz einer Knotenuberdeckung mit hochstens k Knoten) auf das Cliquenproblem(Frage nach der Existenz einer Clique der Große mindestens |V | − k) reduzierenlasst und umgekehrt (im Karpschen Sinne).In obiger Notation haben wir (fur beide Reduktionsrichtungen!):


f(G) = Gc und, fur V ′ ⊆ V, g(G, V ′) = V \ V ′

Diese Approximationsreduktion erhalt aber nicht die Approximationsgute:Betrachte die Graphenschar (Gn)n≥1, wobei Gn aus zwei Cliquen mit jeweils nKnoten besteht, wobei der i-te Knoten der ersten Clique mit allen Knoten derzweiten Clique —mit Ausnahme des i-ten Knoten der zweiten Clique— verbundenist. Jede maximale Clique von Gn enthalt n Knoten.

Der Komplementgraph Gcn besteht aus n disjunkten Paaren miteinander verbun-

dener Knoten. Daher hat die triviale Losung des MVC-Problems (man nehme alleKnoten als Knotenuberdeckung) eine Leistungsgute von 2. Geht man zuruck zumUrsprungsproblem, dem Cliquenproblem, so ware die der MVC-Leistung ”entspre-chende“ Cliquenlosung die leere Menge.Damit ist klar, dass die Naherungsgute nicht erhalten bleibt bei dieser Reduktion.

Definition 15.10 Betrachte P1,P2 ∈ NPO, P1 heiß naherungserhaltend aufP2 reduzierbar, kurz P1 ist AP-reduzierbar (AP bedeutet ausgeschrieben ”ap-proximation preserving“) auf P2, in Zeichen P1 ≤AP P2, wenn es zwei Abbildungenf , g gibt und eine Konstante α ≥ 1 derart, dass folgende Bedingungen erfullt sind:

1. ∀x ∈ IP1∀r ∈ Q ∩ (1,∞) : f(x, r) ∈ IP2 .

2. ∀x ∈ IP1∀r ∈ Q ∩ (1,∞) : SP1(x) 6= ∅ → SP2(x)(f(x, r)) 6= ∅.

3. ∀x ∈ IP1∀r ∈ Q ∩ (1,∞)∀y ∈ SP2(f(x, r)) : g(x, y, r) ∈ SP1(x).

4. f , g sind durch Algorithmen Af , Ag berechenbar, deren Laufzeit polynomiellist fur jedes feste r ∈ Q ∩ (1,∞).

5. ∀x ∈ IP1∀r ∈ Q ∩ (1,∞)∀y ∈ SP2(f(x, r)) :

RP2(f(x, r), y) ≤ r → RP1(x, g(x, y, r)) ≤ 1 + α(r − 1)

Ein einfaches Beispiel fur eine AP-Reduktion liefern MAXCLIQUE und MAX-ISdurch Ubergang auf den Komplementgraphen; die Clique wird so zur unabhangigenMenge.

Satz 15.11 Betrachte P1,P2,P3 ∈ NPO.

1. Gilt P1 ≤AP P2 und P2 ≤AP P3, so auch P1 ≤AP P3 (Transitivitat)

2. Gilt P1 ≤AP P2 und P2 ∈ APX, so folgt P1 ∈ APX.

3. Gilt P1 ≤AP P2 und P2 ∈ PTAS, so folgt P1 ∈ PTAS.

Beweis:

1. Ist intuitiv klar, wenn auch formal muhsam hinzuschreiben.


2. Sei (f, g, α) eine AP-Reduktion von P1 auf P2. Liegt P2 in APX und ist AP2

ein Algorithmus fur P2 mit Leistungsgute hochstens r, so ist

AP1(x) := g(x,AP2(f, (x, r)), r)

ein Polynomzeitalgorithmus der Leistungsgute hochstens 1 + α(r − 1).

3. Entsprechend uberlegt man fur Approximationsschemata, dass

AP1(x, r) = g(x,AP2(f(x, r′), r′), r′)

mit r′ = 1+(r−1)/α ein Approximationsschema fur P1 ist, sobald AP2 einesfur P2 ist. 2

Wegen Satz 15.11.1 ist die folgende Definition sinnvoll:

Definition 15.12 Es sei C ⊆NPO.Ein Problem P[∈ NPO] heißt C-hart, wenn fur jedes P ′ ∈ C gilt:

P ′ ≤AP P.

Ein C-hartes Problem heißt C-vollstandig, wenn es in C liegt.

Bemerkung 15.13 In der Literatur werden verschiedene Reduktionsbegriffe furApproximationsprobleme betrachtet. Entsprechend gibt es auch verschiedene Harte-und Vollstandigkeitsbegriffe. Naheres dazu im Buch von Ausiello et al., Kapitel 8!

Im Folgenden werden wir noch einige konkrete AP-Vollstandigkeitsbegriffe disku-tieren. Dadurch wird auch der Umgang mit AP-Reduktionen geubt.

15.4 NPO-Vollstandigkeit

Als (nahezu generische) NPO-vollstandige Probleme betrachten wir:

a) MAXWSAT fur Maximierungsprobleme aus NPO,

b) MINWSAT fur Minimierungsprobleme aus NPO.

Konkreter: MAXWSAT (Maximum Weighted Satisfiability)

I : Boolesche Formeln ϕ mit Variablen x1, . . . , xn undnichtnegativen Gewichten w1, . . . , wn

S : Belegung I der Variablen, sodass ϕ erfullt wird.m : max {1,

∑ni=1 wiτ(xi)}; hierbei werden durch τ die Booleschen Werte

true und false mit 1 und 0 identifiziert.opt : max


MINWSAT ist das entsprechende Minimierungsproblem (opt = min).

Mitteilung 15.14 a) MAXWSAT ist vollandig fur die Klasse der Maximierungs-probleme in NPO.

b) MINWSAT ist vollstandig fur die Klasse der Minimierungsprobleme in NPO.

Der Beweis der Mitteilung ist analog zum Beweis des Satzes von Cook-Levin: DerRechenteppich einer geeigneten Turingmaschine wird ”logisch ausgedruckt“.

Aus der Mitteilung alleine folgt nicht, dass MAXWSAT oder MINWSAT NPO-vollstandig sind. Dies ergibt sich aber unmittelbar aus dem folgenden Satz.

Satz 15.15 MAXWSAT und MINWSAT sind aufeinander AP-reduzierbar.

Beweis: (Skizze) Wir beschreiben genauer eine Reduktion von MAXWSAT aufMINWSAT, die hinsichtlich Bedingung 5 keine AP-Reduktion ist, da das sich erge-bende ”α“ von r abhangt, also nicht konstant ist. Danach deuten wir an, wie sich dieKonstruktion als Spezialfall einer Schar von Reduktionen deuten lasst; mindestenseine Reduktion aus dieser Schar ist auch eine AP-Reduktion. In ahnlicher Weisekann man eine AP-Reduktion von MINWSAT auf MAXWSAT angeben.

Konstruktion einer ”falschen“ AP-Reduktion von MAXWSAT auf MINWSAT: Ausdem (nur angedeuteten) Beweis der vorigen Mitteilung ergibt sich, dass wir o.E. nurMAXWSAT-Instanzen mit Boolescher Formel betrachten mussen, die das Folgendeerfullen:

1. ϕ ist definiert uber Variablen v1, . . . , vs mit Gewichten w(vi) = 2s−i, i =1, . . . , s sowie uber einigen anderen Variablen vom Gewicht Null.

2. Jede Belegung, die ϕ erfullt, weist wenigstens einer der vi den Wert true zu.

Es sei x eine solchermaßen eingeschrankte Instanz von MAXWSAT mit BoolescherFormel ϕ. Definiere:

f(x) := ϕ ∧ α1 ∧ . . . ∧ αs mit αi := (zi ≡ (v1 ∧ . . . ∧ vi−1) ∨ vi));

zi sind dabei neue Variablen mit w(zi) = 2i, 1 ≤ i ≤ s. Alle anderen Variablenhaben Gewicht Null in der f(x)-Instanz.Ist y eine erfullende Belegung fur f(x), so sei g(x, y) die Einschrankung von y aufdie in ϕ vorkommenden Variablen.

Beachte: Genau eine der zi-Variablen ist true in jeder erfullenden Belegung vonf(x). Ware keine der zi-Variablen true, dann waren auch alle vi-Variablen falsch,was 2. widerspricht. Nach Konstruktion der αi sind aber keine zwei zi-Variablen


wahr.Also gilt fur jede zulassige Losung y von f(x), dass m(f(x), y) = 2i fur ein 1 ≤ i ≤ s.

m(f(x), y) = 2i ⇔ zi = 1⇔ v1 = v2 = . . . vi−1 = 0 ∧ vi = 1⇔ 2s−i ≤ m(x, g(x, y)) < 2 · 2s−i

;2s

m(f(x), y)≤ m(x, g(x, y)) < 2 · 2s

m(f(x), y)

fur jede zulassige Losung y von f(x). [∗]

Dies gilt naturlich auch fur eine optimale Losung y∗f von f(x).Ist y eine zulassige Losung fur x, also eine erfullende Belegung von ϕ, so gibt eswegen 2) ein kleinstes i, fur das vi true ist. Durch zi = true und zj = false fur j 6= ilasst sich diese Belegung zu einer erfullenden Belegung y von f(x) erweitern. Eineroptimalen Losung y∗ von x entspricht so eine zulassige Losung y

∗von f(x) mit der

Eigenschaft g(x, y∗) = y∗.

Fur die Leistungsgute von g(x, y) ergibt sich:

R(x, (x, y)) =m∗(x)

m(x, g(x, y))=

m(x, y∗)m(x, g(x, y))

[∗]<

2 · 2s

m(f(x),y∗)

2s

m(f(x),y)

≤ 2 ·m(f(x), y)m∗(f(x))

= 2 ·R(f(x), y).

Setzen wir diese Abschatzung in der letzten Bedingung der AP-Reduktions-Definitionein, so sehen wir, dass α = (2r− 1)/(r− 1) keine Konstante ist. Betrachte nun fol-gende Schar von Reduktionen:

fk(x) := ϕ ∧∧

i=1,...,s

b1=0,1,...,bk=0,1

αi,b1,...,bk

mit

αi,b1,...,bk= (zi,b1,...,bk

≡ (v1 ∧ . . . ∧ vi−1 ∧ vi ∧ (vi+1 ≡ b1) ∧ . . . ∧ (vi+k ≡ bk)))

(Falls i + j > s, entfallen die entsprechenden Bedingungen vi+j ≡ bj .)Dafur sind zi,b1,...,bk

2k · s viele neue Variablen.Wie oben sind nur die z-Variablen solche mit nicht-verschwindendem Gewicht. Wirsetzen hierbei

w(zi,b1,...,bk) =

⌈c · 2s

w(vi) +∑k

j=1 bjw(vi+j)

⌉fur eine genugend große Konstante c.

Nach einiger (hier fortgelassener) Rechnung findet man

c · 2s

m(fk(x), y)≤ m(x, g(x, y)) <

c · 2s

m(fk(x), y)· (1 + 2−k)

Dabei ist g(x, y) wieder durch ”Vergessen“ der z-Belegung definiert.Wie zuvor erhalt man somit

R(x, g(x, y)) < (1 + 2−k)R(fk(x), y).


Unsere zuvor durchgefuhrte Rechnung entspricht dem Spezialfall k = 0. Ist nunr > 1 vorgegeben, so wahlen wir k so, dass 2−k ≤ (r − 1)/r.Dann folgt aus R(fk(x), y) ≤ r namlich

R(fk(x), y) < (1 + 2−k)R(fk(x), y) ≤ r + r2−k ≤ r + r − 1 = 1 + 2(r − 1).

Mit f(x, r) := fkr (x) ist (f, g, 2) eine AP-Reduktion von MAXWSAT auf MINW-SAT. 2

Folgerung 15.16 Maximum Weighted 3-SAT ist NPO-vollstandig.

Beweis: Die Uberfuhrung in KNF ist in Polynomzeit moglich, ansonsten betrachteden Beweis von Lemma 15.4. 2

Analog sieht man

Folgerung 15.17 Minimum Weighted 3-SAT ist NPO-vollstandig. 2

Folgerung 15.18 Minimum {0, 1}-LP ist NPO-vollstandig.

Beweis: Kombiniere Folgerung 15.17 und (den Beweis von) Lemma 15.3. 2

15.5 EXP-APX-Vollstandigkeit

Der Unterschied zwischen EXP-APX und NPO besteht darin, dass fur NPO-ProblemeP die Menge SP(x) fur jede Instanz x NP-hart sein darf (und in den vorigen Bei-spielen fur NPO-vollstandige Probleme auch war). Dadurch, dass man ”kunstlich“die Menge der zulassigen Losungen trivialisiert, ohne die optimalen Losugen zuverandern, kann man sich Probleme definieren, fur die man EXP-APX-Vollstandigkeitbeweisen kann.

Bemerkung 15.19 Der Nachteil der hier betrachteten NPO- bzw. der daraus ab-geleiteten EXP-APX-vollstandigen Probleme ist ihre ”Kunstlichkeit“.Wir werden abschließend APX-vollstandige ”naturliche“ Probleme kennen lernen.

15.6 APX-Vollstandigkeit

Mit Hilfe der uns hier nicht zur Verfugung stehenden PCP-Kennzeichnung von NPlasst sich zeigen (s. das Buch von Ausiello et al.).

Mitteilung 15.20 MAX 3-SAT ist vollstandig fur die Klasse der Maximierungs-probleme in APX.


Daraus folgt zusammen mit dem folgenden Satz, dass MAX 3-SAT tatsachlich APX-vollstandig ist.

Satz 15.21 Zu jedem Minimierungsproblem P ∈ APX gibt es ein Maximierungs-problem P ′ ∈ APX mit P ≤AP P ′.

Beweis: (Skizze) Es sei A eine r-Approximation von P. Definiere P ′ wie P bis aufdie Maßfunktion, die wie folgt definiert ist:

mP′(x, y) ={

(dremP(x,A(x))− (dre ·mP(x, y)), mP(x, y) ≤ mP(x,A(x))mP(x,A(x)), sonst

; mP(x,A(x)) ≤ m∗P′(x) ≤ (dremP(x,A(x))

→ A ist (dre+ 1)-Approximation fur das Maximierungsproblem P ′.

Die AP-Reduktion ist wie folgt definiert:

1. Fur jede Instanz x setze f(x) = x.

2. Fur jede Instanz x und fur jede Losung y von f(x):

g(x, y) ={

y, mP(x, y) ≤ mP(x,A(x))A(x), sonst

3. α = dre+ 1.

Um nachzuweisen, dass diese Reduktion wirklich eine AP-Reduktion ist, betrachteeine Losung y mit R′

P , (x, y) = m∗P′(x)/mP(x, y) ≤ r′.

Zu zeigen ist:RP(x, g(x, y)) ≤ 1 + α(r′ − 1)

Dies kann durch Unterscheidung der Falle mP(x, y) ≤ mP(x,A(x)) bzw. mP(x, y) >mP(x,A(x)) durch einige Abschatzungen hergeleitet werden. 2

L-Reduktionen—Motivation Wie kann man nun APX-Vollstandigkeit fur

”naturliche“ Probleme beweisen? Hierbei ist es manchmal hilfreich, sich ”alte“ be-kannte NP-Vollstandigkeitsbeweise fur die betreffende Entscheidungsprobleme an-zusehen. So wird fur das Kantenschnittproblem ublicherweise (siehe das Buch vonAusiello et al.) der Weg von 3-SAT uber MAX2SATD, NOT-ALL-EQUAL-3SATzu MAXCUTD gegangen.Hierbei ist es haufig hilfreich, eine andere als die bislang diskutierte AP-Reduktionzu betrachten, da sich dabei NP-Reduktionen leichter ubertragen:

Definition 15.22 Es seien P1 und P2 zwei NPO-Probleme. P1 heißt L-reduzierbarauf P2, i. Z. P1 ≤L P2, wenn zwei Funktionen f, g und zwei positive Konstantenβ, γ existieren, sodass:

1. ∀x ∈ IP1 : f(x) ∈ IP2 ist in Polynomzeit berechenbar.


2. ∀x ∈ IP1 : SP1(x) 6= ∅ → SP2(f(x)) 6= ∅.

3. ∀x ∈ IP1∀y ∈ SP1(f(x)) : g(x, y) ∈ SP1(x) ist in Polynomzeit berechenbar.

4. ∀x ∈ IP1 : m∗P2

(f(x)) ≤ βm∗P1

(x).

5. ∀x ∈ IP1∀y ∈ sP2(f(x)) :∣∣m∗P1

(x)−mP1(x, g(x, y))∣∣ ≤ γ ·

∣∣m∗P2

(x)−m∗P2

(f(x), y)∣∣

(f, g, β, γ) heißt auch L-Reduktion von P1 auf P2 .

Mitteilung 15.23 Es seien P1,P2 ∈ NPO mit P1 ≤L P2. P1 ∈ APX → P1 ≤AP

P2.

Als eine Anwendung und erstes Glied obiger Reduktionskette zeigen wir:

Satz 15.24 MAX3SAT ≤L MAX2SAT.

Beweis: Wir geben einer L-Reduktion (f, g, 13, 1) an. Es sei ϕ eine Instanz vonMAX3SAT mit m Klauseln ai ∨ bi ∨ ci, 1 ≤ i ≤ m, wobei ai, bi und ci Literale sind.Jeder dieser Klauseln ordnen wir die folgenden zehn neuen Klauseln zu (jede hathochstens zwei Literale!):

(∗) ai, bi, ci, di, ai ∨ bi, ai ∨ ci, bi ∨ ci, ai ∨ di, bi ∨ di, ci ∨ di

1 2 3 4 5 6 7 8 9 10

Dabei ist di eine neue Variable. f(ϕ) = ϕ′ sei die sich so ergebende Instanz vonMAX2SAT.Die folgende Tabelle zeigt, dass jede Belegung hochstens 7 der 10 Klauseln einerGruppe der Form (∗) erfullt (symmetrische Falle sind nicht aufgefuhrt)

ai bi ci di 1 2 3 4 5 6 7 8 9 10∑

0 0 0 0 1 1 1 1 1 1 60 0 0 1 1 1 1 1 40 0 1 0 1 1 1 1 1 1 1 7←0 0 1 1 1 1 1 1 1 1 60 1 1 0 1 1 1 1 1 1 1 7←0 1 1 1 1 1 1 1 1 1 1 7←1 1 1 0 1 1 1 1 1 1 61 1 1 1 1 1 1 1 1 1 1 7←

Fur jede erfullende Belegung der ursprunglichen 3-SAT-Klausel ai ∨ bi ∨ ci gibtes eine Belegung von (∗), die sieben Klauseln erfullt; diese sind durch Pfeile inder Tabelle markiert. Wegen der ersten Zeile der Tabelle gibt es im Falle einerai ∨ bi ∨ ci nicht-erfullenden Belegung eine Belegung von di, die 6 Klauseln von (∗)erfullt. Somit konnen wir schließen:

m∗(ϕ′) = 6m + m∗(ϕ) ≤ 12m∗(ϕ) + m∗(ϕ) = 13m∗(ϕ).


Die Ungleichung gilt, da zu einer KNF-Formel stets eine Belegung existiert, diewenigstens die Halfte der Klausel erfullt (siehe Analyse der Greedy-Heuristik furMAXSAT in Satz 11.9).

Ist τ ′ eine Belegung der Variablen von ϕ′, so bezeichne τ = g(ϕ, τ ′) die Restriktionvon τ ′ auf die in ϕ vorkommenden Variablen. Durch Betrachten obiger Tabelleergibt sich

m(ϕ, τ) ≥ m(ϕ′, τ ′)− 6m.

Damit haben wir:

|m∗(ϕ)−m(ϕ, g(ϕ, τ ′))| = m∗(ϕ)−m(ϕ, τ)= m∗(ϕ′)− 6m−m(ϕ, τ)≤ m∗(ϕ′)− 6m−m(ϕ′, τ ′) + 6m

= |m∗(ϕ′)−m(ϕ′, τ ′)| .2

15.7 Facetten der Harte fur Approximationen

Diese Darstellung folgt:D.S. Johnson: The NP-Completeness Column: The Many Limits on Approximation.ACM Trans. Alg., Band 2, S. 473–489, 2006.

Der “Goldstandard” fur Harteresultate:Ist betrachtetes Optimierungsproblem “leicht” (das hangt von der konkreten Klasseab, die man betrachtet), so folgt P = NP.

Beispiel 15.25 Dinur und Safra konnten 2002 (ECCC, dann SODA 2005) zeigen:Falls P 6= NP, so lasst sich das Knotenuberdeckungsproblem nicht besser als 1.36067approximieren.

Diese Aussage lasst noch eine betrachtliche Lucke, denn das beste bekannte positiveApproximationsergebnis stammt von Karakostas (ICALP 2005):Das Knotenuberdeckungsproblem fur n-Knotengraphen lasst sich in der Leistungsgute2−Θ( 1√

log(n)) approximieren.

Unter schwacheren Annahmen lassen sich manchmal starkere Aussagen gewinnen.

Intuitive Ahnlichkeit von Problemen

Bekannt: Das Cliquenproblem.Feige et al. konnte 2006 zeigen (J.ACM Band 43, Seiten 268–292):

Mitteilung 15.26 MAXCLIQUE lasst sich nicht mit einem Faktor 2(log(n))1−ε

ap-proximieren fur irgendein ε > 0, falls nicht NP ⊆ DTIME (npolylog(n)).

Unter starkeren Voraussetzungen (Goldstandard) kann man eine schwachere Aus-sage zeigen:


Mitteilung 15.27 Gilt P 6= NP, so lasst sich MAXCLIQUE fur kein ε > 0 aufeinen Faktor von n1−ε approximieren.

Gelten ahnliche Schranken fur ahnliche Probleme ?Leider nicht immer. . .

Sehr ahnlich zu dem Problem des Findens großer Cliquen scheint doch das Problemzu sein, moglichst große ausgeglichene Bicliquen zu finden. Dies bedeutet genauer:

Ein vollstandiger bipartiter Graph Kk,` heißt auch Biclique. Eine Biclique heißtausgeglichen, falls auf beiden Seiten der Bipartition gleichviele Knoten liegen.

Das Problem, moglichst große ausgeglichene Bicliquen in einem (nicht notwendig bi-partiten) Graphen zu finden, ist bekanntermaßen NP-hart (auch bekannt als BCBS:balanced complete bipartite subgraph).

BCBS-Approximation

Oft begegnen wir Approximationsschranken, die randomisierte Komplexitatsklassenbetreffen.BP steht fur “bounded error probabilistic”.Details zu dieser und vielen anderen Komplexitatsklassen finden Sie unter Komple-xitats-Wiki am Caltech.

Mitteilung 15.28 BCBS lasst sich nicht mit einem Faktor nδ approximieren furein bestimmtes δ > 0, falls nicht NP ⊆

⋂ε>0 BPTIME(2nε

).

Eine ahnliche Approximationsschranke konnte Feige 2002 unter einer anderen An-nahme zeigen, namlich unter der sogenannten Durchschnittsfallharte von 3SAT.Auch hier kommt aber wieder eine Randomisierung ins Spiel.

Label Cover: ein hubsches Hilfsproblem

Eine Instanz wird beschrieben durch:einen bipartiten Graphen G = (V1, V2;E), E ⊆ V1 × V2,naturliche Zahlen N,M,B,Abbildungen πu,v : {1, . . . ,M} → {1, . . . , N} fur jede Kante (u, v) ∈ E.Frage: Gibt es Knotenmarkierungen L1 : V1 → {1, . . . ,M} und L2 : V2 → {1, . . . , N},sodass mindestens B Kanten abgedeckt sind ?Hierbei ist eine Kante (u, v) abgedeckt durch die Markierung, falls πu,v(L1(u)) =L2(v).

Arora und Lund konnten 1997 zeigen, dass die Maximierungsvariante von LabelCover hart zu approximieren ist fur jeden konstanten Faktor, wenn nicht P = NP.Arora und Lund konnten genauer folgendes zeigen:Zu jedem 0, 5 > ε > 0 gibt es eine Konstante k(ε), sodass fur alle Instanzen vonLabel Cover mit M,N ≤ k(ε) die nachstehend beschriebenen zwei Falle NP-hartzu unterscheiden sind:(1) Es gibt eine Markierung, die alle Kanten abdeckt.(2) Es gibt keine Markierung, die mehr als ε · |E| viele Kanten abdeckt.

http://qwiki.caltech.edu/wiki/Complexity_Zoo

http://qwiki.caltech.edu/wiki/Complexity_Zoo


Die so entstandene Lucke wird im Beweis der in der vorigen Folie gezeigten Be-hauptung verwendet.endslide

Unique Game Conjecture (UGC) ist ein seltsamer Name fur eine Einschrankungvon Label Cover; tatsachlich wurden Label Cover und die Unique Game Conjecturezunacht in Termini von Spielen definiert.

Vermutung (UGC): Fur alle ε, δ ∈ (0; 1/2) gibt es eine Konstante k(ε, δ), sodassfur Label Cover Instanzen mit M = N = k(ε, δ), in denen daruber hinaus dieAbbildungen πu,v samtlich Permutationen sind, es keinen Polynomzeit-Algorithmusgibt, der unterscheiden kann zwischen(1) Es gibt eine Markierung, die wenigstens (1 − δ)|E| viele Kanten abdeckt und(2) Es gibt keine Markierung, die mehr als ε · |E| viele Kanten abdeckt.

Viele Forscher bezweifeln (noch) die Gultigkeit der UGC.

Konsequenzen der UGC: Khot und Regev konnten 2003 zeigen:

Mitteilung 15.29 Gilt die UGC, so gibt es keinen Algorithmus, der das Kno-tenuberdeckungsproblem auf einen konstanten Faktor besser als 2 approximiert.

Noch uberraschender ist das Ergebnis fur MaxCut:Hierbei wird fur einen gegebenen Graphen G = (V,E) nach einer Knotenmenge Sgesucht, die die Zahl der Kanten mit genau einem Endpunkt in S maximiert.Goemans und Williamson haben 1995 einen (komplizierten) α-Faktor-Approxima-tionsalgorithmus gefunden mit α = min0<θ≤π(π(1− cos(θ))/(2θ)).Unter der Annahme der UGC ist dieser Faktor bestmoglich !

Die Approximationstheorie lasst noch viele weiter hubsche Ergebnisse und auchmanche Uberraschungen in den nachsten Jahren erwarten. Bleiben Sie am Ball !

Documents

Uni Trierfernau/Nalg0607/version1.pdf · INHALTSVERZEICHNIS 2 Inhaltsverzeichnis 1 Einfuhrung 7¨ 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Das