Black Box Algorithmen
Hartmut KlauckUniversität FrankfurtSS 05
29.4.
Approximationsalgorithmen
Viele wichtige Optimierungsprobleme sind NP-schwer TSP, Clique, Vertex Cover ....
Statt exakter Optimierung nur approximative Lösung
Optimierungsproblem: Eingabeinstanz (z.B. Graph) Lösungen (z.B. Cliquen) Kostenfunktion c (z.B. Grösse der Clique)
Berechne eine Lösung mit maximaler/minimaler Kostenfunktion
Approximationsalgorithmen
Konzentrieren auf Maximierungsprobleme auf Graphen
Qualität einer Lösung P auf einem Graphen G mit optimaler Lösung Osei c(P)/c(O)
Definition 6.1.:Ein Algorithmus ist ein-Approximationsalgorithmus, wenn er für ein Graphmaximierungsproblem zu jedem Eingabegraphen G eine Lösung mit Qualität mindestens findet.
Interessant, wenn Algorithmus effizient, aber exakte Optimierung schwer
Beispiel
Clique problem Eingaben: Graphen Lösungen: Cliquen Optimum: Grösse der grössten Clique NP-schwer Approximation mit Faktor 1/n1- is immer
noch schwer [Hastad97] Letzte Vorlesung: Finden grosse
approximative Cliquen in linearer Zeit in der Anzahl der Knoten
Max Cut
Max Cut Problem: Eingabe: Graph Lösung: Partition der Knoten in zwei Mengen Kostenfunktion: Anzahl der kreuzenden
Kanten NP-schwer
Sei für eine Partition (V1, V2) der Knoten e(V1, V2) die Anzahl der Kanten mit einem Endpunkt in V1, einem in V2
(V1,V2)=e(V1,V2)/n2
Maximiere: (G)=max (V1,V2)
Max Cut
Sei für eine Partition (V1, V2) der Knoten e(V1, V2) die Anzahl der Kanten mit einem Endpunkt in V1, einem in V2
(V1,V2)=e(V1,V2)/n2
Maximiere: (G)=max (V1,V2) Insbesondere ist immer (G) < 0.5
Max Cut
Lange bekannt: Polynomieller Approximationsalgorithmus mit Qualität 1/2.
[Goemans Williamson 94]: Polynomieller Algorithmus mit Qualität 0.878 Darstellung als semidefinites Programm,
Lösung, Randomisiertes Runden der reellwertigen Lösung
PCP-Theorie: Kein polynomieller Algorithmus ist besser als 0.944
Wahrscheinlich 0.878 optimal
Berliebig nahe Approximation? Auf dichten Graphen:
Wenn es (n2) Kanten gibt, ist eine1--Approximation in polynomieller Zeit möglich [AKK96, dlV96]
Ein PTAS [polynomial time approximation scheme] ist eine Familie von Algorithmen, abhängig von , die für jedes konstante eine 1- Approximation in polynomieller Zeit erlauben
Max Cut
Max Cut hat allgemein kein PTAS Auf dichten Graphen aber doch
Property Tester
Eigenschaft p-Cut: G hat (G)>p p-Cut: Akzeptiere, wenn (G)>p,
verwerfe, wenn G -weit entfernt, d.h., wenn n2 Kanten hinzugegeben werden müssen, um (G)>p zu erreichen
Offensichtlich sind das Kanten über den Cut!
Also weit weg: (G)<p-
Property Testing vs. Approximation
Normalerweise: Begriff -weit ergibt ganz neues Problem (vergl. Clique)
Hier: Tester entscheidet mit Gap Übung: Tester (Entscheidung mit Gap
für alle p) erlaubt auch Approximation des optimalen Wertes der Kostenfunktion
Kann man p-Cut testen?
Property Testing für Max Cut
Theorem 6.2: Es gibt einen Property Tester für p-Cut, für
p<1/2-(1), der mit poly(1/) Fragen und Zeit exp(1/) auskommt.
In Zeit exp(1/)+O(n/poly(1/)) kann ein Cut gefunden werden, der nur n2 Kanten weniger als der maximale Cut hat
Auf Graphen mit (n2) Kanten hat Max Cut ein Approximationsschema (PTAS)
Plan
Zeigen den zweiten Punkt (mit schlechterer Laufzeit), und folgern dann den Property Tester
Dritter Punkt: wenn G mindestenscn2 Kanten hat, hat der maximale cut mindestens cn2/2 Kanten, und wenn wir einen Cut mit (G)n2-‘n2 Kanten finden, ergibt ein Algorithmus mit ‘= c/2 „fehlenden Kanten“ eine Approximation mit Qualität
Ein Greedy Algorithmus
Starte mit einem Cut Wenn es einen Knoten gibt, der mehr Nachbarn auf
seiner Seite als auf der anderen hat, verschiebe ihn Etc.
Sei (v,S) der Grad von Knoten v in Knotenmenge S, d.h. die Anzahl der Nachbarn von v in S
Partition V1, V2
Wechsel für v in V1 also wenn (v,V1)> (v,V2)
Schnelle Approximation für Max Cut
Problem: Greedy Algorithmus liefert keine sehr gute Approximation
Weiterhin: Wollen nicht Grade exakt berechnen, da im Tester nicht möglich
Approximiere Grad durch Sampling
Schnelle Approximation für Max Cut Orakel-Algorithmus:
Gegeben sei ein Orakel, dass für einen Knoten anzeigt, wieviele Nachbarn er auf einem maximalen cut in der Menge V1 und wieviele in V2 hat.
Plaziere den Knoten entsprechend Klar: Es ergibt sich ein maximaler Cut Problem 1: Haben so ein Orakel nicht Lösungsansatz: Ziehen Samplemenge S, nehmen an
wir haben optimalen Cut auf S hoffen auf gute Approximation der Grade, teilen v danach auf
Tatsächlich: durchlaufe alle cuts aus S
Schnelle Approximation für Max Cut: Erster Ansatz
Also:Ziehe kleine Samplemenge S aus V
Betrachte alle Partitionen S1, S2
Erzeuge jeweils Partition V1, V2, wobei v in V1, gdw. (v,S2)> (v,S1)
Wähle besten Cut Hoffnung: für richtige Partition S1, S2
werden Grade in S repräsentativ sein
Schnelle Approximation für Max Cut Problem mit dem Ansatz: Kanten ausserhalb von S unberücksichtigt Beispiel: Gebe es eine grosse Clique mit p2n2 Kanten
Max Cut zerschneide Clique S wird m.h.Ws. Clique sampeln, d.h. ca. pS Knoten
aus der Clique haben. Max Cut in S zerschneidet die Teilclique in zwei
gleiche Teile Wenig Information, auf welche Seite restliche Knoten
der Clique sollen, Grad in beiden Hälften gleich!
Schnelle Approximation für Max Cut Problem des Ansatzes ist, dass eine Menge S für zu
viele (nämlich alle) Knoten verwendet wird! Eigentliche Umsetzung der sampling Idee wäre es für
jedes v eine eigene Menge S zu nehmen!
Kompromiss: Verwende 4/ Mengen von n/4 Knoten Für jede Menge verwende eine Samplemenge S,
durchlaufe alle Partitionen von S und bestimme Grade von den Knoten bezüglich S
Immer noch konstant viele Iterationen
Schnelle Approximation für Max Cut
Vergesse Approximation der Grade im Moment
Was passiert, wenn viele Knoten gleichzeitig die Seite wechseln?
Schnelle Approximation für Max Cut Im maximalen Cut gilt, dass für jeden einzelnen Knoten ein
Wechsel der Seite keine Verschlechterung/Verbesserung des Cuts ergibt
Betrachte Knotenmenge der Grösse n/4, und wechsele jeden Knoten anhand seines Grades im Restgraphen:
H1,H2 sei der maximale Cut X sei Menge von n/4 Knoten, W sei V-X Partition W1,W2 auf W Für alle v in X tue v nach W1, wenn Grad in W1 kleiner als in
W2 Dabei kann der Cut verkleinert werden! Aber nur um |X|2, wenn Kanten nach W optimal gewählt Also Verschlechterung nur 2 n2/16, nicht ( n2) 1/ solche Schritte vertretbar, Verlust (n2) gesamt
Schnelle Approximation für Max Cut Neuer Orakel-Algorithmus:
Knoten seien in l=4/ Teilmengen der Grösse n/4 partitioniert, beliebig, Mengen V1, Vl
Fixiere einen Max Cut H1, H2
Für jede Menge Vi durchlaufe alle Knoten in Vi, Orakel gibt an Grad in Wi
1, Wi2, dem von
H1, H2 induzierten Cut in V-Vi, partitioniere so VI
Ergebnis: höchstens (1/)¢ 2 n2/16= n2/16 Kanten weniger im Cut als in H1, H2
Schnelle Approximation für Max Cut
Weiteres Vorgehen:Ersetze jetzt Orakel durch Sample
ansatz, wähle Mengen U1,…,Ul
Benutze Ui für Vi, Ui µ V-Vi
Durchlaufe alle Partitionen von Ui, partitioniere Knoten in Vi entsprechend nach Grad
Schnelle Approximation für Max Cut Also angenommen Ui erlaubt gute Approximation Max Cut sei H1, H2, induziert cut W1,W2 auf V –Vi
Ui sei in Ui1,Ui
2 partitioniert V 2 Vi wird nach Grad aufgeteilt Verlust |Vi|2 wie im Orakel Algorithmus Zusätzlich: Balancierte Knoten, bei denen der Grad in W1,
W2 fast gleich (bis auf n/8) werden schlecht approximierten Grad haben, bei beliebiger Aufteilung ergibt sich ein Verlust von (4/)( n/4)( n/8)= n2/8 Kanten, also OK
Müssen zeigen, dass U‘s so gewählt werden können, dass bei Gradunterschied > n/8 richtig approximiert wird
Der Algorithmus
Verwende beliebige feste Partition von V in l=4/ gleich grosse Mengen V1,…,Vl
Ziehe U1,…, Ul, wobei Ui uniform aus V-Vi ist, mit Grösse O(1/2¢ log(1/))
Durchlaufe alle Tupel U11,U1
2,…,Ul1,Ul
2 von Partitionen der Ui
Partitioniere Vi, indem jeder Knoten v nach V1
i geht, wenn (v,Si1)< (v,Si
2)
Bestimme die Partition mit dem besten Cut
Analyse
Laufzeit ist 2poly(1/) mal O(n2)
Korrektheit: Lemma 6.3.:
Sei H1,H2 eine beliebige Partition von V Dann existiert mit Wahrscheinlichkeit 5/6
über Wahl der Ui eine Partition U11,U1
2,…,Ul
1,Ul2 , auf der der Algorithmus eine
Partition V1,V2 berechnet, die (V1,V2)¸ (H1,H2)- ¾ erfüllt