Methoden des
Algorithmenentwurfs
Kapitel 1.3: Approximation mit
relativer Güte
Christian Scheideler
SS 2009
02.12.2015
Kapitel 1
1
Übersicht
•
•
•
•
•
Notation
Das metrische TSP Problem
Unabhängige Mengen
Bin Packing
Nichtapproximierbarkeit
02.12.2015
Kapitel 1
2
Notation
3.1 Definition: Sei P ein Optimierungsproblem und A ein
Approximationsalgorithmus für P.
(a) A hat bei Eingabe I eine relative Güte von
rA(I) = max{ A(I)/OPT(I), OPT(I)/A(I) }
Für ein Minimierungsproblem ist der erste Term
dominant und für ein Maximierungsproblem der
zweite.
(b) Die relative worst-case Güte von A ist die Funktion
rAwc(n) = max { rA(I) | ID, |I|  n}
(c) Sei rA:IN  IN eine Funktion. A garantiert eine
relative Güte von rA(n) falls für alle n gilt:
rAwc(n)  rA(n).
02.12.2015
Kapitel 1
3
Notation
3.1 Definition (Forsetzung):
(d) A macht bei Eingabe I einen relativen Fehler von
eA(I) = |A(I)-OPT(I)| / OPT(I)
A garantiert einen relativen Fehler von eA(n) falls für
alle ID mit |I|n gilt: eA(I)  eA(n).
(e) Sei r´A:IN  IN eine Funktion. A hat eine relative
Abweichung von r´A(n), falls für unendlich viele n gilt
r´A(n)  rAwc(n).
Eine unendlich große Menge D´, D´D, heißt
r´A(n)-Zeugenmenge gegen A, wenn für alle ID´ gilt:
rA(I)  r´A(|I|). Eine solche Eingabe nennen wir dann
einen r´A(n)-Zeugen.
02.12.2015
Kapitel 1
4
Notation
3.2 Bemerkung: Sei P ein Optimierungsproblem und A ein Approximationsalgorithmus für P.
(a)Bei einem Minimierungsproblem ist
1+eA(n) = rA(n).
(b)Bei einem Maximierungsproblem ist
1-eA(n) = 1/rA(n).
(c)Für beide Problemtypen ist
eA(n)  rA(n)-1.
02.12.2015
Kapitel 1
5
Notation
Ziele:
• Finde Approximationsalgorithmen mit
möglichst kleiner relativer Güte.
• Zeige (asymptotisch) übereinstimmende
Werte für die relative Güte und relative
Abweichung.
02.12.2015
Kapitel 1
6
Das Metrische TSP Problem
Allgemeines TSP Problem: Gegeben der vollständige Graph Kn mit Kostenfunktion c:EIN, finde
einen Hamilton-Kreis mit minimalen Kosten.
Bemerkung: TSP ist ein NP-hartes Problem.
02.12.2015
Kapitel 12
7
Das Metrische TSP Problem
Eine natürliche Einschränkung des TSPs ist das
folgende Problem:
TSP: Gegeben der Graph Kn mit Metrik c:EIN,
bestimme einen Hamilton-Kreis mit minimalen
Kosten.
Eine Metrik muss die Dreiecksungleichung erfüllen,
d.h. u,v,wV: c(u,v)  c(u,w)+c(w,v)
Bemerkung: Dieses Problem ist immer noch NP-hart,
kann aber mit konstanter Güte approximiert werden.
02.12.2015
Kapitel 12
8
Das Metrische TSP Problem
Einfüge-Heuristik:
• Idee: erweitere Tour nach und nach durch Hinzufügung eines
neuen Knotens.
• Einfügeoperation für Tour C=(u1,...,uk,u1):
Algorithmus Einfüge(C,v)
(1) bestimme i, so dass c(ui,v)+c(v,ui+1)-c(ui,ui+1) minimal ist
(2) gib (u1,..., ui,v,ui+1,...,uk,u1) aus
ui+1
Erhöhung von c(C) durch v:
c(ui,v)+c(v,ui+1)-c(ui,ui+1)
v
ui
02.12.2015
Kapitel 1
9
Das Metrische TSP Problem
Klasse der Einfüge-Heuristiken:
Algorithmus EH
C1:=(v1,v1) für einen beliebigen Knoten v1
for j:=2 to n do
(*) wähle einen Knoten vj, der nicht in Cj-1 ist
Cj:=Einfüge(Cj-1,vj)
Beachte, dass in (*) offen geblieben ist, wie vj
ausgewählt wird. (v1,...,vn) heißt die EinfügeAbfolge und beschreibt die Wirkung des Algorithmus vollständig (sofern die Einfügestellen in
Einfüge() eindeutig sind).
02.12.2015
Kapitel 1
10
Das Metrische TSP Problem
3.4 Satz: Jede Einfüge-Heuristik EH garantiert
EH(Kn,c)(log n+1)OPT(Kn,c).
Beweis:
• Sei (v1,...,vn) eine beliebige Einfüge-Abfolge.
• Sei cost(vj) die Verlängerung der Tour durch vj,
d.h. cost(vj) = c(Cj)-c(Cj-1).
• Mit cost(v1)=0 haben wir folgende Teleskopsumme:
cost({v1,...,vn}) = Sj=1n cost(vj)
= Sj=1n (c(Cj)-c(Cj-1))
= c(Cn) = EH(I)
• Um fortzufahren, benötigen wir folgendes Lemma.
02.12.2015
Kapitel 1
11
Das Metrische TSP Problem
3.5 Lemma: Für alle vivj gilt:
min{cost(vi),cost(vj)}  2c(vi,vj)
Beweis:
• O.B.d.A. sei i<j. Sei x der Nachfolger von vi in Tour Cj-1
• In Cj-1 wird vj an einer Stelle eingefügt, für die die
Verlängerung minimal ist.
• Also ist sie höchstens so groß, als würde vj zwischen
vi und x eingefügt, d.h.
cost(vj)  c(vi,vj)+c(vj,x)-c(vi,x)
• Zudem gilt wegen der Dreiecksungleichung:
c(vi,vj)+c(vi,x)  c(vj,x), also c(vj,x)-c(vi,x)  c(vi,vj)
• Daraus folgt cost(vj)  2c(vi,vj) und damit das Lemma.
02.12.2015
Kapitel 1
12
Das Metrische TSP Problem
• Sei R*=(w1,...,wn,w1) eine optimale Tour für I
und R=(wi1,wi2,...,wik,wi1) ein Kreis aus k
Knoten auf I mit ij<ij+1. R ist an R* angelehnt,
also kein beliebiger Kreis.
• Wegen der Dreiecksungleichung gilt
c(R) ≤ c(R*) = OPT(I)
• Wir zeigen jetzt, dass man aus jedem an
einer optimalen Tour angelehnten Kreis ca.
die Hälfte der Knoten so auswählen kann,
dass deren Kosten gemäß der gegebenen
EH-Heuristik höchstens OPT(I) sind.
02.12.2015
Kapitel 1
13
Das Metrische TSP Problem
3.6 Lemma: Seien R* und R wie oben. Dann gibt es eine
Menge Z {wi1,wi2,...,wik,wi1} mit |Z|=k/2 und cost(Z) 
OPT(I).
Beweis:
• R wird in zwei Mengen aufgeteilt (wenn k ungerade ist,
fehlt die letzte Kante des Kreises):
M1={{wi1,wi2},{wi3,wi4},…} und
M2={{wi2,wi3},{wi4,wi5},…}
• Es ist |M1|=|M2|= k/2
• Sei M dasjenige Mi, für das c(Mi) ≤ c(R)/2 ≤ c(R*)/2 ist
• Sei Z die Menge der Knoten, die pro Kante in M den
kleineren cost-Wert haben
• Die Wahl von Z hängt von EH-Heuristik ab
02.12.2015
Kapitel 1
14
Das Metrische TSP Problem
3.6 Lemma: Seien R* und R wie oben. Dann
gibt es eine Menge Z {wi1,wi2,...,wik,wi1}
mit |Z|=k/2 und cost(Z)  OPT(I).
Beweis (Fortsetzung):
• Es ist |Z|=k/2 und wegen Lemma 3.5,
cost(Z) = S {wij,w j+1}M min{cost(wij),cost(wij+1)}
 S {wij,w j+1}M 2c(wij,wij+1) = 2c(M)
 2c(R)/2  OPT(I)
i
i
02.12.2015
Kapitel 1
15
Das Metrische TSP Problem
• Anfangs setzen wir R1=R*.
• Dann bestimmen wir Z1 gemäß Lemma 3.6 und
berechnen R2=R1-Z1.
• Allgemein bestimmen wir sukzessive Zi gemäß
Lemma 3.6 und berechnen Ri+1=Ri-Zi, bis Ri nur noch
aus einer Kante (mit Kosten max. OPT(I) ) besteht.
• Wie man leicht sieht, ist |Ri| ≤ n/2i-1+1 für alle i, so
dass der Prozess oben nach höchstens log n+1
Runden terminiert.
• Die Gesamtkosten sind also
cost({v1,…,vn}) = cost( i Zi) = Si cost(Zi)
≤ (log n +1)  OPT(I)
02.12.2015
Kapitel 1
16
Das Metrische TSP Problem
• Bis heute ist nicht bekannt, ob Satz 3.4 scharf ist.
Man kennt allerdings Auswahl-strategien mit
relativer Abweichung W(log n / log log n)
• Es gibt aber auch Auswahlstrategien mit relativer
Güte 2. Dazu wird als Knoten v immer derjenige
Knoten gewählt, der am nächsten zu einem
Knoten in Cj-1 ist.
• Der resultierende Algo heißt dann
NearestInsertion.
3.7 Satz: NearestInsertion garantiert bei Eingaben
über n Knoten eine relative Güte von 2-2/n.
02.12.2015
Kapitel 1
17
Das Metrische TSP Problem
• Die NearestInsertion Heuristik ist identisch
mit einem Algorithmus von Christofides.
• Dieser Algorithmus basiert auf der
Berechnung eines minimalen
Spannbaums und einer Euler-Tour durch
diesen. Dazu zunächst einige Definitionen.
02.12.2015
Kapitel 1
18
Exkurs: Minimaler Spannbaum
Zentrale Frage: Welche Kanten muss ich
nehmen, um mit minimalen Kosten alle
Knoten zu verbinden?
1
3
2
3
2
2
5
2
1
02.12.2015
3
4
Kapitel 1
19
Exkurs: Minimaler Spannbaum
Eingabe:
• ungerichteter Graph G=(V,E)
• Kantenkosten c:EIR+
Ausgabe:
• Teilmenge TE, so dass Graph (V,T) verbunden
und c(T)=eT c(e) minimal ist
• T formt immer einen Baum (wenn c positiv).
• Baum über Knoten in V mit minimalen
Kosten: minimaler Spannbaum (MSB)
02.12.2015
Kapitel 1
20
Exkurs: Minimaler Spannbaum
3.8 Lemma: Sei (U,W) eine Partition von V
(d.h. UW = V und UW = ) und e={s,t}
eine Kante mit minimalen Kosten mit sU
und tW. Dann gibt es einen minimalen
Spannbaum (MSB) T, der e enthält.
s
U
02.12.2015
e
Kapitel 1
t
W
21
Exkurs: Minimaler Spannbaum
Beweis:
• Betrachte beliebigen MSB T´
• e={s,t}: (U,W)-Kante minimaler Kosten
s
e
U
t
W
e´
in T´
• Ersetzung von e´ durch e führt zu Baum T´´, der
höchstens Kosten von MSB T´ hat, also MSB ist
02.12.2015
Kapitel 1
22
Exkurs: Minimaler Spannbaum
Problem: Wie wandelt man Lemma 3.8 in einen
effizienten Algorithmus um?
Strategie von Jarnik/Prim:
• Starte bei beliebigem Knoten s, MSB T besteht
anfangs nur aus s
• Ergänze T sukzessive durch eine günstigste Kante
von T zu einem Knoten w, der noch nicht in T ist,
bis T alle Knoten im Graphen umfasst
Laufzeit bei geeigneter Implementierung:
O(|V| log |V| + |E|)
02.12.2015
Kapitel 9
23
Exkurs: Minimaler Spannbaum
Beispiel:
1
3
2
3
2
s
2
1
02.12.2015
2
5
3
4
Kapitel 9
24
Exkurs: Euler-Tour
Ein (Multi-)Graph G heißt Eulersch, wenn es in G einen
Kreis gibt, der jede Kante von G genau einmal durchläuft
(eine sogenannte Euler-Tour oder Euler-Kreis).
3.9 Lemma: G ist Eulersch genau dann, wenn G zusammenhängend ist und jeder seiner Knoten geraden Grad
hat.
Beweis:
: klar
: durch Induktion über die Kantenzahl
• Da alle Knoten Grad 2 haben, gibt es einen Kreis C in
G. (Fange bei beliebigem Knoten an und wandere entlang beliebiger Kanten, bis ein Knoten zum zweitenmal
besucht wird.)
02.12.2015
Kapitel 12
25
Exkurs: Euler-Tour
Beweis (Fortsetzung):
• Seien G1,…,Gk die ZHKs von G nach Entfernung der
Kanten in C. Da C ein Kreis ist, sind die Knotengrade in
jedem Gi gerade. Nach der Induktion gibt es also einen
Euler-Kreis Ci in jedem Gi.
• Diese Euler-Kreise und Kreis C können leicht an Schnittstellen zu einem Euler-Kreis von G zusammengesetzt
werden.
C1
C2
C3
C
02.12.2015
Kapitel 12
26
Exkurs: Euler-Tour
• Der Beweis zum Lemma kann in einen
Algorithmus umgewandelt werden, der
eine Euler-Tour in Zeit O(|V|+|E|)
berechnet.
• Jetzt sind wir soweit, Christofides´ ersten
Algorithmus zum TSP Problem
vorzustellen.
02.12.2015
Kapitel 1
27
Das Metrische TSP Problem
Betrachte den folgenden Algorithmus für das
TSP-Problem mit Metrik c:
CH1-Algorithmus:
1. Berechne einen minimalen Spannbaum T von
(V,c).
2. Verdopple alle Kanten in T zum Multigraph T*.
3. Konstruiere einen Euler-Kreis K von T*.
4. Entferne in K Wiederholungen von Knoten, so
dass sich ein Hamilton-Kreis C ergibt.
5. Gib C aus.
02.12.2015
Kapitel 12
28
Das Metrische TSP Problem
2
1
2
2
2
1
1
T
2
2
2
2
1
1
1
2
2
C
1
2
1
2
1
K
1
02.12.2015
1
1
Kapitel 12
29
Das Metrische TSP Problem
3.10 Satz: Der CH1-Algorithmus ist eine 2(1-1/n)-Approximation des TSPs.
Beweis:
• Der CH1-Algorithmus ist in poly. Zeit implementierbar.
• Für eine Kantenmenge E sei c(E) = eE c(e).
• Da c eine Metrik ist, gilt c(C)  c(K)
(C entsteht ja aus K über “Abkürzungen”.)
• Nach der Konstruktion von T* gilt c(K) = c(T*) = 2c(T)
• Sei C* die optimale Lösung des -TSPs. Löschen wir
eine beliebige Kante {v,w} in C*, so ist C* ein Spannbaum in G. Also gilt c(T)  c(C*\{v,w})  (1-1/n) c(C*),
falls {v,w} die teuerste der Kanten in C* ist.
• Damit folgt c(C)  2(1-1/n)c(C*)
02.12.2015
Kapitel 12
30
Das Metrische TSP Problem
Ist der CH1-Algorithmus bestmöglich?
Nein. Christofides hat auch einen verbesserten Algorithmus
vorgestellt, bekannt als Christofides´ Algorithmus.
Dazu brauchen wir weitere Definitionen.
• Ein Matching M eines Graphen G=(V,E) ist eine Menge
von Kanten, in jeder Knoten höchstens einmal
vorkommt.
• Ein perfektes Matching M ist eine Menge von Kanten, in
der jeder Knoten genau einmal vorkommt.
• Ein perfektes Mathing M mit minimalem Kantengewicht
nennen wir ein leichtestes Matching.
02.12.2015
Kapitel 12
31
Das Metrische TSP Problem
Beispiele:
Matching
02.12.2015
perfektes Matching
Kapitel 1
32
Das Metrische TSP Problem
3.11 Lemma:
(a) In jedem Graphen G ist die Anzahl der
Knoten ungeraden Grades gerade.
(b) Für jedes (V,c) mit geradem |V| kann ein
leichtestes Matching in O(n2,5(log n)4) Zeit
gefunden werden (zeigen wir hier nicht).
Beweis von (a):
• Für alle Graphen G=(V,E) gilt v deg(v) =
2|E|. v deg(v) ist also gerade.
• Sei U die Menge der Knoten in G mit ungeradem Grad. Dann ist auch vU deg(v)
gerade und damit |U| gerade.
02.12.2015
Kapitel 1
33
Das Metrische TSP Problem
Christofides´ Algorithmus:
1. Berechne einen MSB T zu (V,c).
2. Bestimme die Menge U der Knoten ungeraden
Grades in T. (|U| ist nach Lemma 3.11 gerade,
besitzt also ein perfektes Matching.)
3. Berechne ein leichtestes Matching M für (U,c).
4. Sei G=(V, TM). (Alle Knoten haben damit
geraden Grad.) Konstruiere in G einen EulerKreis K.
5. Entferne in K Wiederholungen, so dass
Hamilton-Kreis C verbleibt.
6. Gib C aus.
02.12.2015
Kapitel 1
34
Das Metrische TSP Problem
3.12 Satz: Christofides´ Algorithmus ist eine (3/2-1/n)-Approximation
des TSP.
Beweis:
• Wie für den Beweis des CH1-Algorithmus gilt
c(C)  c(K) = c(G) = c(T)+c(M)
• Zu zeigen: c(M)  c(C*)/2 für einen optimalen Hamilton-Kreis C*.
• Sei C*=(v1,v2,…,vn) und U=(vi1,…,vim). Betrachte die Matchings
M1 = { {vi1,vi2}, {vi3,vi4},…,{vim-1,vim} }
M2 = { {vi2,vi3}, {vi4,vi5},…,{vim,vi1 } }
• Wegen der Dreiecksungleichung gilt
M1
C*
c(M1)+c(M2)  c(C*)
• Aus der Minimalität von M folgt:
2c(M)  c(M1)+c(M2)  c(C*)
M2
• Also ist
c(C)  c(T)+c(M) (1-1/n)c(C*) + c(C*)/2 = (3/2-1/n)c(C*)
02.12.2015
Kapitel 1
35
Das Metrische TSP Problem
Die Analyse von Christofides´ Algorithmus ist scharf, wie
der folgende Satz zeigt. Es wird jedoch vermutet, dass
eine 4/3-Approximation für das TSP existiert.
3.13. Satz: Sei n gerade. Gbad(n) ist ein (3/2-1/n)-Zeuge
gegen Christofides´ Algorithmus.
n/2+2
6
5
n
4
3
1
2
Gbad(n). Die eingezeichneten Kanten haben Länge 1.
02.12.2015
Kapitel 1
36
Das Metrische TSP Problem
Beweis:
• Da alle nicht eingezeichneten Kanten Länge
>1 haben, ist R*=(1,2,…,n,1) eine optimale
Rundreise, d.h. OPT(Gbad)=n.
• Minimaler Spannbaum T:
n/2+2
6
5
n
• Kosten: c(T)=n-1
02.12.2015
4
3
1
2
Kapitel 1
37
Das Metrische TSP Problem
Beweis (Fortsetzung):
• Alle Knoten in T haben ungeraden Grad.
• Leichtestes Matching:
n/2+2
6
5
n
• Kosten: c(M)=n/2
02.12.2015
4
3
1
2
Kapitel 1
38
Das Metrische TSP Problem
Beweis (Fortsetzung):
• Ein Eulerkreis ist (1,4,5,1,2,3,1,n,6,n1,…,n/2,n/2+5,n/2+1,n/2+4,n/2+2,n/2+3,n/2+4,n/2+5,
…,n-1,n,1).
• Daraus ergibt sich folgende Rundreise:
n/2+2
6
5
n
4
3
1
2
• Die Kosten sind gleich denen des Euler-Kreises, also
(3/2)n-1
02.12.2015
Kapitel 1
39
Übersicht
•
•
•
•
•
Notation
Das metrische TSP Problem
Unabhängige Mengen
Bin Packing
Nichtapproximierbarkeit
02.12.2015
Kapitel 1
40
Unabhängige Mengen
• Es gibt Probleme, bei denen die relative Güte
nicht konstant ist sondern von der Eingabegröße
abhängen kann. Ein Beispiel dafür ist das
Independent Set Problem (IS).
3.14 Definition: Sei G=(V,E) ein Graph und sei UV
eine Knotenmenge. U wird unabhängig genannt,
wenn für alle Knotenpaare u,vU gilt: {u,v}E.
Das IS Problem ist das Problem, zum Eingabegraphen eine möglichst große unabhängige
Menge zu finden.
02.12.2015
Kapitel 1
41
Unabhängige Mengen
• Das IS Problem ist NP-hart und benötigt daher
einen Approximationsalgorithmus.
• Wir untersuchen den folgenden Algorithmus:
Algorithmus GreedyIS:
U:= ;t:=0; V(0):=V
while V(t) do // Runde t
G(t):= der von V(t) induzierte Graph
ut:= ein Knoten mit minimalem Grad in G(t)
(*) V(t+1):=V(t)-({ut}GG(t)(ut))
U:=U{ut}
=:lösch(t)
t:=t+1
gib U aus
02.12.2015
Kapitel 1
42
Unabhängige Mengen
• Offensichtlich berechnet GreedyIS eine
nichterweiterbare unabhängige Menge, und
das in Zeit O(|V|+|E|).
• Wie nah ist diese Menge an einer maximalen
unabhängigen Menge?
3.15 Satz: Sei G=(V,E) eine Eingabe für
GreedyIS. Dann ist rGreedyIS(G)  |E|/|V|+1.
Für planare Graphen ist die relative Güte also
konstant (denn |E|  3|V|-6 ).
02.12.2015
Kapitel 1
43
Unabhängige Mengen
Beweis:
• gt=|lösch(t)|: Anzahl der in Runde t aus G(t) entfernten
Knoten
• U*: maximale unabhängige Menge, d.h. OPT(G)=|U*|
• kt=|U*  lösch(t)|: Anzahl der in dieser Runde
betroffenen Knoten aus U*
• Es gilt:
St=0|U|-1 gt = |V| und St=0|U|-1 kt = OPT(G)
• Wir wollen nun bestimmen, wieviele Kanten durch (*)
aus G(t) mindestens entfernt werden.
• Betrachte dazu zunächst Extremfälle für Knoten ut.
02.12.2015
Kapitel 1
44
Unabhängige Mengen
Beweis (Fortsetzung):
• Extremfälle für ut für Anzahl entfernter Kanten:
Grad gt -1
(a)
ut
 gt -2
Grad gt -1
(b) ut
• In (a) werden mindestens (gt -1)(gt -2) Kanten und in (b) noch
gt (gt -1)/2 Kanten entfernt, was minimal ist.
• Allerdings sind kt Knoten in lösch(t)  U* unabhängig, d.h. sie
dürfen nicht durch Kanten verbunden sein.
• Da diese Kanten außerhalb von lösch(t) enden müssen, ist die
Mindestzahl der gelöschten Kanten also (gt(gt-1)+kt(kt-1))/2.
02.12.2015
Kapitel 1
45
Unabhängige Mengen
Beweis (Fortsetzung):
• Insgesamt gilt also:
St=0|U|-1 (gt(gt-1)+kt(kt-1))/2  |E|
• Ausklammern, Umformen und Einsetzen ergibt:
St=0|U|-1 (gt2+kt2)  2|E|+|V|+OPT(G)
• Diese Ungleichung gilt für beliebige zulässige
Werte für gt und kt und daher insbesondere für
gt=|V|/|U| und kt=OPT(G)/|U|
• Damit und mit GreedyIS(G)=|U| bekommt man
|V|2+OPT(G)2
GreedyIS(G)  2|E|+|V|+OPT(G)
und schließlich OPT(G)/GreedyIS(G)  |E|/|V| +1
02.12.2015
Kapitel 1
46
Unabhängige Mengen
Nebenrechnungen:
02.12.2015
Kapitel 1
47
Unabhängige Mengen
Bei hohem Grad kann GreedyIS sehr schlechte Ausgaben
liefern:
3.16 Satz: GreedyIS hat eine relative Abweichung von
mindestens (|V|-1)/4.
Beweis:
• Betrachte den folgenden Graphen Gbad:
(n-1)/2
………
GreedyIS(Gbad) = 2
(n-1)/2
………
OPT(Gbad) = (n-1)/2
02.12.2015
Kapitel 1
48
Unabhängige Mengen
3.17 Satz: Sei G=(V,E) ein knoten-k-färbbarer Graph
mit k2. Dann ist GreedyIS(G)  logk(|V|/3).
Beweis:
• Wir benötigen dazu das folgende Lemma, das
eine Beziehung zwischen der Anzahl der Farben
und dem minimalen Grad eines Graphen herstellt.
3.18 Lemma: Sei G=(V,E) ein knoten-k-färbbarer
Graph. Dann gibt es ein uV mit
degG(u)  (1-1/k)|V|.
02.12.2015
Kapitel 1
49
Unabhängige Mengen
Beweis (Lemma 3.18):
• Sei G mit k Farben gefärbt und bezeichne Ui
die Menge der Knoten mit Farbe i.
• Ui ist eine unabhängige Menge für alle i.
• Es muss eine Menge U unter den Ui´s geben,
die mindestens |V|/k Knoten enthält.
• Jeder Knoten in U kann nur mit höchstens
|V|-|U| <|V|- |V|/k = (1-1/k)|V| Knoten
außerhalb von U verbunden sein.
02.12.2015
Kapitel 1
50
Unabhängige Mengen
Beweis (Satz 3.17):
• Sei |V|=n und |V(t)|=nt. Es gilt k2.
• Wegen Lemma 3.14 hat ut höchstens (1-1/k)nt Nachbarn.
• Wenn diese zusammen mit ut aus V(t) herausgenommen
werden, ergibt sich:
n0 = n und
nt+1  nt – (1-1/k)nt -1  nt/k – 1
und damit
k 1-1
n -2
nt  n

kt k-1
kt
kt
• In jeder Runde t mit nt1 wird ein neuer Knoten nach U
gelegt. Das geht auf jeden Fall solange, bis t  logk(n/3) ist.
• Damit ist |U|  logk(n/3) .
02.12.2015
Kapitel 1
51
Unabhängige Mengen
• Wie wir oben bemerkt haben, kann man allen
Knoten einer unabhängigen Menge dieselbe
Farbe zuweisen.
• Das nutzen wir jetzt für einen neuen
Algorithmus für das Knotenfärbungsproblem.
• Idee: bestimme mit GreedyIS eine
unabhängige Menge, weise diesen Knoten
eine Farbe zu, lösche die Knoten aus dem
Graphen, und wiederhole das, bis alle Knoten
gefärbt sind.
02.12.2015
Kapitel 1
52
Unabhängige Mengen
Algorithmus GreedyCol2:
t:=1; V(1):=V
while V(t) do
G(t) := der durch V(t) induzierte Graph
Ut := GreedyIS(G(t))
färbe alle Knoten in Ut mit Farbe t
V(t+1):=V(t)-Ut
t:=t+1
gib die Färbung aus
02.12.2015
Kapitel 1
53
Unabhängige Mengen
3.19 Satz: Sei G=(V,E) ein knoten-k-färbbarer
Graph, n=|V|. GreedyCol2 gibt eine Färbung mit
höchstens 3n/logk(n/16) Farben aus und hat eine
relative Gütegarantie von O(n/log n).
Beweis:
• Sei nt=|V(t)|. Wegen Satz 3.17 ist |Ut|  logk(nt/3).
• Das führt zu folgender rekursiver Beziehung:
n1 = n und
nt+1  nt – logk(nt/3)
• Der Algorithmus bricht ab, wenn nt<1 ist. Wir
bestimmen nun, für welches t das eintritt.
02.12.2015
Kapitel 1
54
Unabhängige Mengen
Beweis (Fortsetzung):
• Sei nt  n/logk(n/16). Mit der Beziehung
n/logkn(3/4)n1/2 ergibt sich:
logk(nt/3)  logk(n/3logkn)  logk((n/16)1/2) = logk(n/16)/2
• D.h. solange noch n/logk(n/16) Knoten ungefärbt sind,
werden mindestens logk(n/16)/2 Knoten je Runde
gefärbt.
• Da spätestens nach t=2n/logk(n/16) Runden und damit
verteilten Farben die Anzahl der verbliebenen Knoten
<n/logk(n/16) ist, ist die Gesamtzahl der vergebenen
Farben höchstens 3n/logk(n/16).
• Da k=OPT(G) ist, ist die relative Güte von GreedyCol2
3n/logk(n/16)(1/k) = 3n/log(n/16)(log k/k) = O(n/log n)
02.12.2015
Kapitel 1
55
Übersicht
•
•
•
•
•
Notation
Das metrische TSP Problem
Unabhängige Mengen
Bin Packing
Nichtapproximierbarkeit
02.12.2015
Kapitel 1
56
Bin Packing
Bin Packing Problem:
• Gegeben: Liste L von Zahlen s1,…,snIN und die
Bin Größe SIN
• Gesucht: Eine Partitionierung von {1,…,n} in
Mengen B1,…,Bk mit SjBi sj  S für alle i, so dass
k minimal.
Bemerkung: Die Entscheidungsvariante von Bin
Packing ist NP-hart.
Der Einfachheit halber nehmen wir im Folgenden an:
s1,…,sn[0,1] und S=1 (d.h. der Parameter S ist
nicht mehr notwendig)
02.12.2015
Kapitel 1
57
Bin Packing
Mögliche Strategien:
• Algorithmus FF(L) (First Fit)
for j:=1 to n do
packe sj in Bin Bi mit kleinstem i, in den sj
noch passt
• Algorithmus BF(L) (Best Fit)
for j:=1 to n do
packe sj in Bin Bi mit kleinster ungenutzter
Kapazität, in den sj noch passt
• Algorithmus FFD(L) (First Fit Decreasing)
sortiere die Liste L so, dass s1…sn
wende FF(L) an
02.12.2015
Kapitel 1
58
Bin Packing
3.20 Satz: FF und BF haben eine relative
Abweichung von mindestens 5/3.
Beweis:
• Sei n ein Vielfaches von 18 und 0<d<1/84.
• Definiere L=(s1,…,sn) durch
1/6 – 2d
falls 1 i  n/3
si = 1/3 + d
falls n/3 < i  2n/3
1/2 + d
falls 2n/3 < i  n
• Dann gilt OPT(L)=n/3
02.12.2015
Kapitel 1
59
Bin Packing
Beweis (Fortsetzung):
OPT
FF & BF
1/6-2d
1/6-2d
1/3+d
1/6-2d
1/6-2d
1/2+d
1/3+d
1/6-2d
1/6-2d
1/3+d
1/2+d
1/6-2d
n/3 mal
n/18 mal
n/6 mal
n/3 mal
n/18+n/6+n/3 = 5n/9 = (5/3)(n/3)
02.12.2015
Kapitel 1
60
Bin Packing
Bemerkung: Es ist bekannt, dass die relative Güte von FF und
BF im worst case exakt 17/10 ist. Geht es besser?
3.21 Satz: FFD hat eine Approximationsgüte von 3/2.
Beweis:
• Sei L=(s1,…,sn) mit s1…sn und m=OPT(L).
• Sei r die Anzahl der von FFD erzeugten Bins.
• r=m: fertig
• r>m: Wir zeigen zunächst folgendes Lemma:
3.22 Lemma: Sei sk das erste Element, das in Bm+1 gepackt
wurde. Dann gilt sk1/3.
02.12.2015
Kapitel 1
61
Bin Packing
Beweis (Lemma 3.22):
• Angenommen, sk>1/3.
• Dann gibt es ein hm, so dass jeder Bin Bj mit jh
genau ein Element und jeder Bin Bj mit h<jm genau
zwei Elemente enthält:
….
B1
B2
….
Bh
Bh+1
….
Bm
• Es folgt damit k-h-1=2(m-h) (*).
• Weiter gilt sj+sq>1 für alle jh und j<qk, sonst wäre sq
in Bj gepackt worden.
02.12.2015
Kapitel 1
62
Bin Packing
Beweis (Lemma 3.22):
• Seien B´1,…,B´m die Bins einer optimalen Packung.
• Enthält Bin B´i ein Element sj mit jh, so ist kein
weiteres sq mit 1<qk in B´i packbar.
• Also sind s1,…,sh in verschiedenen Bins B´i, im,
enthalten, und diese Bins enthalten keine Elemente
aus sh+1,…,sk.
• Die restlichen Bins enthalten höchstens zwei
Elemente aus sh+1,…,sk, da sj>1/3 für alle jk.
• Die Elemente sh+1,…,sk benötigen also nach (*)
mindestens (k-h)/2 = m-h+1 weitere Bins.
• Insgesamt werden somit h+(m-h+1)=m+1>m Bins
benötigt, ein Widerspruch zur Definition von m!
02.12.2015
Kapitel 1
63
Bin Packing
Beweis (Satz 3.21):
• Sei st ein Element in Bin Br (zur Erinnerung: FFD(L)=r ).
• Da st1/3 (wegen Lemma ), sind die Bins B1,…, Br-1 zu
mindestens 2/3 gefüllt, andernfalls wäre st in eines dieser Bins
gepackt worden.
• Dasselbe Argument zeigt auch, dass h(Br-1)+st > 1
(h(Bi): Last von Bin Bi).
• Insgesamt erhalten wir
Si=1n si  Si=1r-1 h(Bi)+st = Si=1r-2 h(Bi)+(h(Br-1)+st) > (2/3)(r-2)+1
• Da m=OPT(L)  Si=1n si , folgt
OPT(L)  (2/3)(r-2)+1 = (2/3)r-1/3
und damit r  (3/2)OPT(L) +1.
02.12.2015
Kapitel 1
64
Übersicht
•
•
•
•
•
Notation
Das metrische TSP Problem
Unabhängige Mengen
Bin Packing
Nichtapproximierbarkeit
02.12.2015
Kapitel 1
65
Nichtapproximierbarkeit von TSP
3.23 Satz: TSP hat keine r-Approximation für alle
Konstanten r>1, es sei denn, P=NP.
Beweis:
• Betrachte das Hamilton-Kreis (HK) Problem:
Gegeben ein ungerichteter Graph G=(V,E),
entscheide, ob G einen Hamilton-Kreis besitzt
oder nicht.
• Es ist bekannt, dass es NP-hart ist, das HKProblem zu entscheiden.
• Wir wollen mithilfe des HK-Problems zeigen,
dass dann auch Satz 3.23 gilt.
02.12.2015
Kapitel 12
66
Nichtapproximierbarkeit von TSP
Beweis (Fortsetzung):
• Betrachte eine beliebige Konstante r>1.
• Für eine Instanz G=(V,E) des HK-Problems definieren
wir eine Distanzfunktion d mit
d(v,w) =
1
falls {v,w}E
rn
sonst
• Falls G einen Hamilton-Kreis hat, dann gibt es eine
Lösung des TSPs (V,d) der Länge n.
• Hat G keinen Hamilton-Kreis, muss jede Lösung des
TSPs (V,d) mindestens eine Kante {v,w} verwenden, die
nicht in E ist, kostet damit also mehr als rn.
02.12.2015
Kapitel 12
67
Nichtapproximierbarkeit von TSP
Beweis (Fortsetzung):
• Angenommen, es gibt eine r-Approximation A zum TSP.
Dann verwende den folgenden Algorithmus für das HKProblem:
Gegeben ein Graph G=(V,E), konstruiere (V,d) wie oben
und wende A darauf an. Falls A einen Kreis zurückgibt
mit Länge rn, gib “Ja” aus und sonst “Nein”.
• Dieser Algorithmus könnte dann das HK-Problem in
polynomieller Zeit entscheiden, ein Widerspruch zur
Tatsache, dass das HK-Problem NP-hart ist!
• Also kann es keine r-Approximation für das TSP geben,
es sei denn, P=NP.
02.12.2015
Kapitel 12
68
Nichtapprox. von Bin Packing
3.24 Satz: Bin Packing hat keine r-Approximation mit r<3/2, es
sei denn, P=NP.
Beweis:
• Betrachte das NP-harte Entscheidungsproblem Partition:
Gegeben eine Menge S={a1,…,an} natürlicher Zahlen, gibt es
Partition S=S1S2, so dass SaiS1 ai = SaiS2 ai?
• Angenommen, es gibt einen Algo A für Bin Packing mit
relativer Güte kleiner als 3/2.
• Sei S={a1,…,an} eine Instanz von Partition und T:=Si=1n ai. Ist
T ungerade oder gibt es ein ai mit ai>T/2, so kann es keine
Partition geben (da a1,…,anIN sind).
• Sonst sei L=(2a1/T,…,2an/T) eine Instanz von Bin Packing
und m die Anzahl der von A benötigten Bins für L.
• Wir unterscheiden zwei Fälle.
02.12.2015
Kapitel 1
69
Nichtapprox. von Bin Packing
Beweis (Fortsetzung):
• Fall 1: Ist m3, so gilt wegen m/OPT(L)<3/2, dass
OPT(L)>2. Die Elemente in L können also nicht in
zwei Bins der Größe 1 gepackt werden, d.h. die
Antwort für L bzgl. Partition ist „Nein“.
• Fall 2: Ist m2, so folgt wegen Si=1n 2ai/T = 2
sofort, dass m=2. Insbesondere sind dann beide
vom Algorithmus gepackten Bins voll, und die
Antwort für L bzgl. Partition lautet „Ja“.
• Also wäre mittels A das Partition Problem in
polynomieller Zeit entscheidbar, was der Tatsache
widerspricht, dass Partition NP-hart ist.
02.12.2015
Kapitel 1
70
Nichtapproximierbarkeit
Allgemein kann man zeigen:
3.25 Satz: Sei LS* ein NP-vollständiges Entscheidungsproblem und sei P ein Minimierungsproblem. Gibt es
zwei in Polynomzeit berechenbare Funktionen f:S*D
und c:S* IN und eine Konstante g>0, so dass für alle
Eingaben xS* gilt:
 c(x)
xL
OPT(f(x))  c(x)(1+g)
xL
dann gibt es keinen polynomiellen Approximationsalgorithmus der relativen Güte r mit r<1+g, es sei
denn, P=NP.
02.12.2015
Kapitel 1
71
Fragen?
02.12.2015
Kapitel 1
72

Grundlagen der Algorithmen und Datenstrukturen Kapitel 3.3-3.5