Also, Algorithmen 2, Kapitel Approximationsalgorithmen, das machen wir
heute fertig und das wird auch weniger als 90 Minuten dauern und dann
machen wir heute direkt hinten dran die Übung dazu noch und morgen
geht es dann mit etwas anderem los.
Und weil ich das das letzte Mal tatsächlich falsch auf der Folie hatte
und falsch erzählt habe, nochmal, sicherheitshalber, was ist ein NP
-schweres Problem?
Also ein Problem heißt NP-schwer und das muss jetzt kein
Entscheidungsproblem sein, dieses Problem, das ist ruhig ein
Suchproblem, das heißt NP-schwer.
Wenn das so schwer ist, dass, wenn man eine Lösung für das Problem
hätte, auch alles in NP, die ganzen Entscheidungsprobleme in
Polynomialzeit lösbar wären.
Also Pi ist NP-schwer, wenn es ein NP-vollständiges
Entscheidungsproblem L gibt, mit der Eigenschaft, Sie können eine
Turing -Maschine bauen, die in Polynomialzeit läuft und das
Entscheidungsproblem L, das NP-vollständige in Polynomialzeit löst und
damit das klappt, muss es irgendwie Magie haben, eine Glaskugel, sowas
heißt dann Orakel und in dem Fall jetzt eben dann ein Orakel für Pi,
da kann die Orakel-Turing-Maschine eine Probleminstanz von dem Problem
Pi auf das Orakel-Band schreiben und dann sagen Orakel, sag mir die
Antwort und dann in einem Schritt kommt die Antwort für die
Probleminstanz von Pi und wenn Sie das haben, wenn Pi so schwierig
ist, dass, wenn Sie ganz schnell das Orakel befragen können, dann
können Sie das NP-vollständige Problem L auch in Polynomialzeit lösen.
Gut, das ist NP-schwer, damit das nochmal einmal richtig gesagt wurde.
So, und den Rest der Vorlesung heute wollen wir uns mit dem
Rucksackproblem beschäftigen.
Wo bin ich jetzt hier hingekommen?
Auf den falschen Knopf offensichtlich.
Also, und vorneweg zur Vorbereitung gucken wir uns etwas an, das heißt
Pseudopolynomielle Laufzeit bei Algorithmen und dann das
Rucksackproblem.
Üblicherweise, wenn man ausdrücken will, ein Algorithmus, was für eine
Laufzeit hat er, dann sagt man immer, naja, halt im schlimmsten Fall
für Eingaben der Länge n, so und so lange.
Also, man misst die Zeit in Abhängigkeit von der Größe der
Probleminstanz und die Frage ist, was nimmt man als Größe einer
Probleminstanz und stellt sich jetzt mal der Einfachheit halber Zahlen
vor als Eingaben.
Und das Übliche ist dann zu sagen, auch wenn einem das vielleicht
nicht immer völlig bewusst ist, also die Größe einer Eingabe, das ist
halt die Anzahl Bits, die man braucht, um die Zahl hinzuschreiben.
Also, man stellt sich vor, die Zahlen sind binär, wenn es binär giert,
wie viele Bits brauche ich da?
Also, das sind dann für eine Zahl k, sind es halt so
größenordnungsmäßig log k Bits, die man braucht, um eine Zahl
hinzuschreiben.
Und jetzt ganz normal, bei einem Algorithmus wird man sagen, ja, die
Laufzeit ist polynomiell.
Wenn es ein Polynom gibt, so dass für eine Probleminstanz, also sagen
wir, eine bestimmte Zahl als Eingabe, die Laufzeit eben polynomiell
ist in der Anzahl Bits, die man braucht, um die Zahl hinzuschreiben.
Also, stellen Sie sich vor, Sie haben einen Algorithmus, um Zahlen zu
multiplizieren.
Wenn Sie zwei 32-Bit-Zahlen multiplizieren wollen, dann wollen Sie
irgendwie sagen, ja, die Laufzeit ist irgendwie sowas wie ungefähr 32
zum Quadrat oder so.
Sie wollen nicht sagen, die Laufzeit ist... Sie interessieren sich
nicht dafür, dass die Laufzeit so größenordnungsmäßig 2 hoch 32 mal 2
hoch 32 ist oder so.
Also, das Natürliche ist, bei Zahlen zu sagen, ja, binäre Darstellung.
So misst man normalerweise die Größe von Probleminstanzen.
Aber, man kann ja auch anders.
Und jetzt stellen Sie sich vor, und das ist dann der Fall, wo man
sagt, man hat pseudopolynomielle Laufzeit.
Das ist dann der Fall, wo man sagt, okay, es gibt ein Polynom für jede
Probleminstanz.
Die Laufzeit ist beschränkt durch Polynom von Größe der
Probleminstanz, aber Größe heißt jetzt, die Zahl unäher kodiert.
Also, viele Striche, ja, k-Striche, um die Zahl k zu kodieren.
Das ist eine viel größere, viel längere Kodierung gibt das als binär
offensichtlich, ja, k-Symbole statt log k.
Aber, also, wenn man einen Algorithmus hat, wo dann die Laufzeit eben
für eine Probleminstanz bestänkt ist durch Polynom von unähere
Repräsentation, Größe der unähren Repräsentation der Eingabe, dann
sagt man, das ist pseudopolynomielle Laufzeit.
Diese unähere Kodierung ist im Allgemeinen viel größer, also das ist
eine deutlich schwächere Aussage.
Gut.
Und wofür das gut ist, werden wir dann gleich sehen.
Zwei kleine Punkte, damit Sie da nichts durcheinanderbringen.
Zum einen, also auch wenn man bei pseudopolynomieller Laufzeit davon
redet, man misst die Laufzeit in Abhängigkeit von der unäheren
Repräsentation der Eingaben, Sie müssen sich nicht unbedingt
vorstellen, dass der Algorithmus die Zahlen tatsächlich unäher kodiert
bekommt.
Können Sie machen, aber brauchen Sie nicht, ja.
Können Sie sich ruhig binär das vorstellen.
Die Laufzeit, die erlaubte ist halt größer.
Das andere, bitte verwechseln Sie nicht pseudopolynomiell mit quasi
-polynomiell, das gibt es auch.
Das ist für ganz, in Anführungszeichen, ganz normale binäre Kodierung
von Eingaben.
Und man sagt, ein Algorithmus hat quasi-polynomielle Laufzeit, wenn
sie von der Form 2 hoch Groß O von irgendeiner Potenz von Log N ist.
Ignorieren Sie mal das Groß O und stellen Sie sich vor, diese
Konstante C ist einfach 2, da steht 2 hoch Log N mal Log N.
Und wenn Sie sich noch vorstellen, der Logarithmus ist zur Basis 2, da
steht ja sowas wie N hoch Log N im Wesentlichen.
Und da ahnt man dann, warum das quasi-polynomiell heißt.
Also die Idee ist, N hoch etwas, was keine Konstante ist, aber in
Anführungszeichen schwach wächst.
Das erwähne ich, weil, wann war das?
Letztes Jahr irgendwann jemand sagte, oh, ich habe jetzt einen quasi
-polynomialzeit laufenden Algorithmus für Graphisomorphie.
Das ist ein Problem, da weiß man nicht, dass es in P ist.
Man kann aber auch nicht zeigen, dass es in P vollständig ist,
irgendwie dazwischen in Anführungszeichen.
Und nach einigem Hin und Her und einer Kritik und einer Reparatur sind
jetzt mehr Leute der Ansicht, ja, es gibt tatsächlich einen
Algorithmus, der in quasi-polynomialzeit läuft für Graphisomorphie.
Gut, nur so am Rande.
Das Rucksackproblem.
Sie werden sich wahrscheinlich daran erinnern, kommt ja auch irgendwie
in Algorithmen 1 theoretische Grundlagen vor.
Also man hat n Gegenstände und jedes von denen hat eine Größe.
Jeder von den Gegenständen hat eine Größe.
Manchmal sage ich, glaube ich, auch aus Versehen Gewicht.
Also im Englischen geht das auch durcheinander.
Und deswegen, die Größen heißen hier Wi.
Und man soll zumindest einige von diesen Objekten in einen Rucksack
passen.
Der hat aber nur endliches Fassungsvermögen, das ist W.
Also maximal kriegt man da so viel rein, dass die Summe der Größen Wi
der Objekte, die man reinsteckt, W ist.
Das sind sozusagen die Lösungen bei diesem Suchproblem.
Also Teilmengen so, dass die Summe der Gewichte der Objekte in der
Teilmenge W ist.
Und zusätzlich aber jedes Objekt, wenn Sie das mitnehmen können, das
gibt Ihnen irgendein Profit PI.
Das wird im Allgemeinen mit der Größe nichts zu tun haben.
Es gibt kleine Objekte, die wertvoll sind, große Objekte, die nicht
wertvoll sind.
Und das Ziel ist, den Gesamtprofit der Objekte, die Sie in den
Rucksack reinpacken, zu maximieren.
Sinnigerweise bei den Probleminstanzen, man bestrengt sich darauf,
dass man Objekte anguckt, die so klein sind, dass jedenfalls das
Objekt einzeln als einziges in den Rucksack reinpasst.
Objekte, die so groß sind, dass sie nicht mal alleine reinpassen, kann
man gleich wegschmeißen.
Also O, B, D, A, jedes WI ist kleiner gleich groß W.
Das heißt aber auch, also jedes Objekt können Sie in den Rucksack
packen und das heißt, den Profit, den Ihnen dieses eine Objekt
liefert, dieses PI, das können Sie auf jeden Fall als Profit
erreichen.
Und das heißt insbesondere, das Maximum dieser Einzelprofite, das ist
bestimmt eine untere Schranke für den Gesamtprofit.
Also das, was Sie maximal erreichen können, ist mindestens so groß wie
das Maximum der Profite für ein einzelnes Objekt.
Das merken wir uns mal.
Na gut.
Und jetzt hier vielleicht mal, wie ist das, wenn man die Dinger binär
kodiert, wie ist das, wenn man sie unärkoniert?
Na ja, binär kodiert ist das irgendwie naheliegend.
Die Anzahl N gibt halt Log N Bits, das W kodieren Sie in Log W Bits.
Die einzelnen Gewichte ist halt N mal der Platz, um ein Gewicht zu
kodieren und wie gesagt, O, B, D, A, die WI sind alle kleiner gleich
groß W, also maximal braucht man Log W Bits.
Und die Profite, das ist N mal eine Zahl, die so groß ist, also N mal
die Anzahl Bits für ein Einzelprofit.
Und weil es später noch eine Rolle spielt, schätzen wir das mal nach
oben ab und sagen, okay, die Summe der ganzen PI für I gleich 1 bis N,
die nennen wir mal Pdach.
Und so viele Bits reichen auf jeden Fall, um jeden Profit einzeln
hinzuschreiben.
Also N mal Logarithmus von Pdach reicht bestimmt aus, um die Profite
hinzuschreiben.
Wenn Sie es unnäher kodieren, dann fällt halt überall der Logarithmus
weg.
Und wenn Sie es aufsummieren, dann noch haben Sie seit dem einen Fall
größenordnungsmäßig N mal Log W plus Log Pdach und das andere mal N
mal W plus N mal Pdach.
Rucksackproblem ist schwer.
Also wenn Sie auf die normale Art und Weise Größe von Eingaben messen,
binär, das ist NP-schwer.
Das heißt, bei normaler Messung kennt man halt keinen
Polynomialzeitalgorithmus, aber man kennt einen, der
pseudopolynomielle Laufzeit erreicht.
Da lügt man sich doch in die Tasche.
Ja, manchmal.
Schauen wir gleich.
Jedenfalls NP-schwere Probleme, für die es noch einen
pseudopolynomiellen Algorithmus gibt, die heißen schwach NP-schwer.
Und es gibt auch NP-schwere, für die es sowas nicht gibt oder für die
man zumindest so etwas nicht kennt.
Na gut.
Und wie macht man das mit pseudopolynomieller Laufzeit?
Das ist ganz simpel sozusagen mit sogenannter dynamischer
Programmierung.
Wer erinnert sich an diesen Begriff von früher?
Der eine oder andere schon.
Ja, gut.
Also, was ist die Idee bei dynamischer Programmierung?
Man schreibt sich irgendwie sowas, was Rekursives hin, in
Anführungszeichen, und macht es dann ein bisschen clever, indem man
sozusagen das nicht ausprogrammiert mit Rekursivem aufrufen, sondern
dann womöglich einige Dinge für die gleichen Parameter, weder mehrfach
das aufruft, sondern man schreibt sich das halt gleich immer alles auf
oder rechnet in der Tabelle alle Werte aus.
So.
Und diese Tabelle, für die wir uns jetzt hier interessieren, hat so
Einträge.
Die heißen Groß c von klein i und Groß p.
Das i, das läuft durch die Objektnummern von 1 bis n.
Und das Groß p, das ist ein Profit, den wir mindestens erreichen
wollen.
Das geht also maximal bis Summe aller Profite p-Dach.
So.
Und c, i, p soll... was macht man bei c, i, p?
Also erstens, man sagt, jetzt beschränke ich mich mal auf Objekte mit
den Nummern 1 bis i.
Ich erlaube mir nicht alle, ich erlaube nur die von 1 bis i.
Nur von denen picke ich mir ein paar raus.
Und ich gucke, kann ich mit ein paar von diesen Objekten schon Profit
mindestens Groß p erreichen?
Und wenn es da mindestens eine Möglichkeit gibt, dann schaue ich mir
von den Möglichkeiten noch eine an, die möglichst kleine Größe hat.
Gesamtgröße, ja?
Also das c, i, p soll sein, die kleinste... eine Teilmenge mit
kleinster Gesamtgröße, so dass diese Objekte, also erstens nur aus den
Nummern 1 bis i stammen und zweitens der Gesamtprofit immer noch
mindestens Groß p ist.
Das ist dieses zweite Ding da vorne.
Wenn i gleich 1 ist, das ist sozusagen der Basisfall, dann
interessieren sich also für Teilmengen, wo sie höchstens das Objekt
Nummer 1 benutzen.
Da gibt es nur die leere Menge und die Menge, die das Objekt Nummer 1
enthält.
Mit der leeren Menge werden sie keinen großen Profit erreichen, also
es bleibt einfach nur die Menge, die das Objekt Nummer 1 enthält.
Und dann fragen sie sich, was ist das kleinste Gewicht einer solchen
Menge, also was ist das Gewicht des Objekts Nummer 1, sofern man mit
diesem Objekt Nummer 1 mindestens Profit p erreicht.
Und das heißt, wenn das Groß p so klein ist, dass es kleiner gleich p1
ist, dann erreichen sie mindestens Profit p, sie schaffen ja p1.
Und dann sagen sie, okay, das minimale Gewicht ist also w1.
Und wenn sie aber einen so großen Profit angucken, dass sie den nur
mit Objekt 1 gar nicht erreichen können, dann sagen sie, okay, dieser
Eintrag c1p, der ist unendlich.
Das unendlich ist eine geschickte Wahl, weil wir jetzt gleich
minimieren werden.
Also der Basisfall ist ganz einfach.
Ja, und dann gibt es eben den Fall, wo man sozusagen Rekursionen
macht.
Was ist, wenn sie sich Objekte 1 bis i plus 1 angucken?
Und da suchen sie jetzt also nach Teilmengen dieser Menge der Objekte
von 1 bis i plus 1, so dass der Profit mindestens p ist und die
Gesamtgröße möglichst klein.
Wenn sie sowas gefunden haben, dann gibt es zwei Möglichkeiten.
Da ist das Objekt i plus 1 drin, sie haben es wirklich benutzt, oder
halt nicht.
Wenn sie das Objekt i plus 1 gar nicht benutzt haben, also die beiden
Möglichkeiten gibt es nur.
Und wenn sie für die beiden Möglichkeiten, das Objekt i plus 1 ist
drin und das Objekt i plus 1 ist nicht drin, jeweils gucken dafür, was
ist das Kleinste, was man hinkriegt und von den beiden das Minimum
nehmen, dann haben sie den richtigen Eintrag.
Und wenn das Objekt i plus 1 also nicht in der Teilmenge drin ist,
dann schaffen sie also mit den Objekten 1 bis nur maximal Nummer i
Profit mindestens p.
Und die kleinste Gesamtgröße, mit der sie das schaffen können, das ist
das, was in CIP steht.
Das ist der erste Faktor, oder wie soll ich sagen, die erste
Möglichkeit von den beiden, über die man dann minimiert.
Zweite Möglichkeit, das Objekt i plus 1 ist dabei bei so einer
Teilmenge.
Dann hat man also bei der Größe auf jeden Fall die Größe von Objekt i
plus 1 plus noch ein paar Größen von anderen Objekten.
Und mit dem Objekt i plus 1 schaffe ich auf jeden Fall Profit p i plus
1.
Und das heißt, die restlichen Objekte, da reicht es dann, wenn ich mir
den Fall angucke, dass die insgesamt Profit p minus p i plus 1
erzielen.
Und da gucke ich mir da eine Teilmenge mit möglichst kleinem
Gesamtgröße raus.
Und dann ist dann der zweite Teil hier.
Und das kleinere von beiden ist das Beste, was man schaffen kann.
So, und das ist eine rekursive Formulierung für diese CIP.
Und wenn man Behauptungen, wenn man die Halle hat, dann hat man auch
die Lösung von dem Problem.
Was interessiert einen wirklich?
Also erstens, alle Objekte sind erlaubt.
Das heißt, man guckt sich dann den Fall an, dass i ist n.
Und zweitens, der Profit soll halt möglichst groß sein.
Man muss nur gucken, dass das, was als Mindestgewicht, um diesen
Profit zu erreichen, nötig ist, dass das noch in den Rucksack passt.
Also die Minimalgröße muss dann kleiner gleich Groß W sein.
Und das gibt dann diesen simplen Algorithmus.
Also man steckt rein, das n, das Groß W, den Vektor mit den W i, den
Vektor mit den p i, dann die c.
Und bei den Profiten, also es kann nicht besser werden als Summe aller
Profite überhaupt.
Also man schaut sich das alles nur an bis maximal p dach.
Und dann initialisieren sie die c1p, so wie gerade beschrieben.
Und dann machen sie hier, füllen sie die Tabelle aus, Zeile für Zeile
für i gleich 2 bis n mit dieser Regressionsformel.
Und dann gucken sie am Ende in die cnp und schauen, was ist das größte
p, so das cnp, also das minimale Gewicht, mit dem man das noch
schafft, in den Rucksack passt, kleiner gleich W ist.
Die Laufzeit ist im Wesentlichen dominiert durch diese beiden
ineinandergeschachteten Schleifen.
Das ist n mal p dach.
Und hier nochmal drei Folien zurück.
Also wenn Sie sich vorstellen, wir würden das alles unär kodieren, n
mal p dach, das ist die Größe schon für diese Vektoren pi.
Also diese Laufzeit ist pseudopolynomiel.
So wie es da oben hingeschrieben ist, der Pseudocode, der liefert
Ihnen nur den maximalen Profit, den Sie erreichen können.
Jetzt interessiert einen ja vielleicht noch, wie erreicht man den,
welche Objekte muss ich denn jetzt nehmen.
Ja, dann bohren sie das ein bisschen auf und schleppen bei den cnp
immer nicht nur mit rum, was ist das die kleinste Größe, mit der man
das hinkriegt, sondern auch noch, welche Objekte nehme ich denn.
Haben Sie halt so ein Bitvektor, ja, also am Ende Bitvektor der Länge
n und eine 0 heißt, das Objekt fällt weg und eine 1 heißt, an der
Stelle Objekt i nehme ich.
Die machen Sie halt immer länger und am Ende haben Sie die Lösung.
Und wenn Sie sich vorstellen, also wirklich die Lösung repräsentiert
als so ein Vektor mit den Einsen an den Stellen für die Objekte, die
Sie nehmen.
Wenn Sie dann das Skalarprodukt ausrechnen, der Vektor mit den
Profiten mal der Vektor mit den Nullen und Einsen, das ist also
einfach Summe der Pi mal Xi.
Da wo die Xi 0 sind, die Objekte, die Sie weglassen, der Summand ist
0.
Und die Objekte, die Sie nehmen, da ist das Xi 1, da summieren Sie
gerade die Pi auf, das ist gerade der maximale Profit, den Sie dann
kriegen für diese Lösung.
Das erwähne ich hier, weil wir auf diese Art und Weise gleich noch ein
bisschen rechnen.
Also das müssen Sie sich irgendwie merken.
Dieses Sorte Skalarprodukt, das ist irgendwie der Profit, den Sie
kriegen, wenn Sie eben die Lösung nehmen, die durch diesen Bitvektor X
repräsentiert ist.
Allerdings, also die Laufzeit ist pseudopolynomiell.
Wenn Sie das alles binär repräsentieren, das pdach, das kann halt
deutlich größer sein, als das, was Sie de facto, also was Sie bei
normaler Messung zur Verfügung hätten.
Viel zu groß.
Meistens.
Der Trick kommt gleich.
Wir werden das nämlich trotzdem tatsächlich gleich benutzen, um etwas
zu finden, was man ein vollpolynomielles oder
Vollpolynomialzeitapproximationsschema nennt.
Und da gibt es also erstmal die harmlose Variante ohne das Wort voll
dabei.
Das heißt dann im englischen PITAS, Polynomial Time Approximation
Scheme.
Das kann man für Minimierungs- und für Maximierungsprobleme festlegen.
Da wir hier ein Maximierungsproblem haben, gucken wir im Moment
vielleicht mal da drauf.
Und so ein Approximationsschema, das ist ein Algorithmus, dem geben
Sie immer eine Probleminstanz des Suchproblems, das Sie interessiert
und eine Zahl Epsilon.
Und dann soll der Algorithmus, das habe ich vergessen dahin zu
schreiben, als Lösung eben eine Lösung für das ursprüngliche
Suchproblem liefern.
Punkt 1.
Punkt 2.
Er soll eine Nährungslösung liefern, in dem Sinne, dass die Güte der
Antwort, die der Algorithmus liefert, also das, was der Algorithmus A
für Eingabe I und Parameter Epsilon liefert, die Zielfunktion liefert
Ihnen da beim Maximierungsproblem vielleicht nicht ganz das Optimum,
das F-Stern von I, aber wenn Sie gesagt haben, 5 Prozent beim Epsilon,
dann liefert der Algorithmus Ihnen was, was höchstens 5 Prozent
schlechter ist.
Also die Güte der Antwort des Algorithmus ist mindestens 1 minus
Epsilon mal optimale Antwort F-Stern von I.
Und beim Minimierungsproblem ist es vielleicht nicht ganz klein, ein
bisschen drüber, aber mit höchstens 1 plus Epsilon mal optimale
Lösung.
So, also deswegen Approximationsschema und Polynomialzeit, weil
verlangt wird, dass für jedes Epsilon es ein Polynom gibt, sodass dann
für jede Eingabe gilt, die Laufzeit für diese Probleminstanz I und das
Epsilon ist kleiner gleich dem Polynom ausgewertet an, naja, Größe der
binären naheliegenden Repräsentation der Originalprobleminstanz I.
Also für jedes Epsilon muss es dann ein Problem, so ein Polynom geben.
Wenn das Epsilon, also gefühlt, wenn das Epsilon groß ist, wenn man
weit abweichen darf, geht es wahrscheinlich tendenziell schneller.
Wenn das Epsilon klein ist, hat man gleich ein Polynom von höherem
Grad.
Für jedes Epsilon 1.
Und diese etwas willkürliche, für jedes Epsilon es gibt ein Polynom,
das macht man dann bei vollpolynomiellen Approximationsschema auch
noch weg.
Da verlangt man dann, also was die Approximation betrifft, die gleiche
Forderung wie eben.
Aber jetzt die Laufzeit für so eine Eingabe, eine Probleminstanz I und
so ein Epsilon, müssen Sie abschätzen können, indem Sie ein Polynom,
ein Polynom muss es jetzt tun für alle Epsilon, auswerten.
Und da stecken Sie rein die Größe der naheliegenden Repräsentation von
I binär kodiert und das 1 durch Epsilon.
Die kleiner Epsilon, desto größer 1 durch Epsilon.
Also dann darf man ein bisschen länger rechnen.
Aber das muss polynomiell mit dem 1 durch Epsilon wachsen.
Und nicht irgendwie ganz absurd.
Also ein Beispiel für eine Laufzeit, die ok wäre für ein
vollpolynomielles Approximationsschema, wäre halt so was wie n durch
Epsilon hoch 5 plus n² plus Epsilon hoch minus 42.
Das ist polynomiell in n und das ist polynomiell in 1 durch Epsilon.
Für ein PITAS ohne das full wäre auch noch so was wie n hoch 1 durch
Epsilon ok zum Beispiel.
Aber das ist nicht polynomiell in 1 durch Epsilon.
Deutlich nicht.
Also die Forderung vollpolynomiell ist stärker.
Ja und jetzt wollen wir irgendwie diese Möglichkeit mit dynamischer
Programmierung eine Lösung in pseudopolynomieller Laufzeit zu kriegen.
Wollen wir ausnutzen, um etwas in echtpolynomieller Laufzeit zu
kriegen.
Wie kriegt man das hin?
Ja da muss offensichtlich diese, also die pseudopolynomielle Laufzeit
ist ja n mal p dach.
Das muss irgendwie so klein sein, dass es nicht mehr Platz braucht als
die normale binäre Darstellung.
Und wenn Sie sich das so angucken,
also das p dach darf halt nicht zu groß werden.
Oder anders gesagt dann, also die Einzelprofite, die sollten auch
nicht zu groß sein.
Jetzt, wenn Sie ein Problem haben, eine Probleminstanz mit Gewichten,
die ganz groß sind, jedenfalls manche.
Sie brauchen eine Probleminstanz, wo die Profite nicht ganz groß sind,
sondern nur irgendwie klein.
Und Sie wollen das so machen, dass das hoffentlich dann noch irgendwas
mit dem Originalproblem zu tun hat.
Was würden Sie tun?
Sie runden ein bisschen, Sie schneiden bei allen Profiten ein paar
niedrigstwertige Bits ab.
Sie behalten nur ein paar davon.
Und wenn man das richtig macht, dann klappt es tatsächlich.
Und hier ist ein Algorithmus.
Und wir werden uns dann überlegen, das ist tatsächlich eine voll
polynomielles Approximationsschema für Knapseck.
Also Eingaben, erstens so ein epsilon und zweitens halt das, was eine
Probleminstanz von dem Rucksackproblem beschreibt.
Und jetzt machen wir die Wahrscheinlichkeiten, die PI, die originalen
Wahrscheinlichkeiten kleiner, indem wir durch eine Konstante, das sind
Zeile 4, durch eine Konstante Groß K dividieren und abrunden.
Also wir sind hier immer bei nicht negativen ganzen Zahlen.
Und dieses Groß K, das wählt man sinnigerweise als epsilon mal Groß P
durch n.
Und das Groß P ist der größte der Profite.
Und wenn Sie dann also so ein PI durch das K dividieren, dann teilen
Sie das PI durch den größten Profit, dann kriegen Sie was zwischen 0
und 1.
Dann multiplizieren Sie noch mit 1 durch epsilon, da machen Sie dann
doch wieder hinten noch so ein paar Bits dran.
Und Sie multiplizieren noch mit n, also wenn die PI durch Groß P sind
erst mal zwischen 0 und 1 und mit n multipliziert haben Sie irgendwas
zwischen 0 und n.
Das sind neue Gewichte jedenfalls.
Irgendwie kleiner.
Und dann nehmen Sie einfach das gleiche Groß W, die gleichen Größen WI
und diese neuen PI Strich und machen damit dynamische Programmierung.
So wie wir das gerade gesehen haben.
Da kommt jetzt, stellen Sie sich vor, da kommt jetzt so ein Bitvektor
raus.
Jetzt rede ich immer so über Bitvektoren.
Den nennen wir jetzt mal X Strich, passend zu den PI Strich.
Das ist eine optimale Lösung für die P Strich.
Und jetzt drücken wir die Daumen ganz fest und sagen, na das wird dann
wohl auch für die Originalwahrscheinlichkeiten irgendwie ganz gut
klappen.
Und liefern einfach dieses X Strich als Lösung für das
Originalproblem.
So und jetzt muss man sich zwei Dinge überlegen für vollpolynomielles
Approximationsschema.
Erstens, es liefert eine Y-Approximation und zweitens, die Laufzeit
ist polynomial.
Und zwar echt normal in Anführungszeichen.
Das rechnen wir jetzt halt gerade noch nach.
Der Witz ist jetzt wieder, also dieses X Strich ist jetzt so ein
Bitvektor, das beschreibt so eine optimale Lösung für die
Wahrscheinlichkeiten P Strich.
Das heißt, X Strich ist optimal für P Strich.
Und außerdem taucht irgendwo mal X Stern auf.
Da stellen wir uns vor, das wäre so eine Lösung, die den Profit
maximiert für das Original P, für die Originalwahrscheinlichkeiten.
Das heißt, wenn Sie jetzt die letzte Zeile angucken, hinten das
Skalarprodukt P mal X Strich, das ist der optimale Profit für die
Original P i.
Und die Frage ist, wenn wir jetzt X Strich nehmen, das ist optimal für
die P Strich, und benutzen das und sagen, das ist eine Lösung für die
Originalwahrscheinlichkeiten P, wie groß ist dann das P mal X Strich
im Vergleich zu dem P mal X?
Das wollen wir rauskriegen.
Und da soll rauskommen, ja, maximal 1 plus Epsilon.
1 minus Epsilon kleiner.
Genau, also wir wollen zeigen, das ist ein vollpolymerisches
Approximationsschema.
Und die Behauptung ist, mit diesen Bezeichnungen wie eben, wenn Sie
das X Strich, was also die optimale Lösung für P Strich ist, nehmen
und sagen, nehmen wir das als Lösung für die
Originalwahrscheinlichkeiten in P, was Sie dann kriegen, ist
vielleicht nicht das Optimum P mal X Stern, aber mindestens 1 minus
Epsilon P mal X Stern.
Das ist das Wesentliche, was man auch noch was tun muss, und dass die
Laufzeit polynomial ist, ist ganz harmlos.
So, das passt auf eine Folie, das ist im Prinzip gar nicht schwierig,
man muss nur an einigen Stellen so ein bisschen drüber nachdenken,
warum das jetzt wirklich gilt.
So, also wir fangen an mit P mal X Strich oben links und wollen
rauskommen ganz unten in der letzten Zeile und dazwischen immer größer
gleich 1 minus Epsilon mal P mal X Stern.
So, P mal X Strich, das ist also so ein Skalarprodukt, da addieren Sie
einige Pi auf.
Wenn Sie jetzt statt der Pi die K mal Pi Strich nehmen und die Pi
Strich sind Pi durch K abgerundet, dann machen Sie also aus den Pi ein
bisschen was kleineres.
Das heißt, das P mal X Strich ist größer gleich, dann können Sie das K
aus diesem Vektor rausziehen, das ist also ein bisschen mehr als K mal
P Strich mal X Strich.
So, gut.
Dann P Strich mal X Strich, naja, also das X Strich haben wir ja
gekriegt als optimale Lösung für das P Strich.
Das heißt, wenn Sie jetzt eine andere Lösung als das X Strich nehmen,
zum Beispiel das X Stern, dann kriegen Sie halt etwas, was bestenfalls
genauso gut ist, vielleicht schlechter.
Das X Stern ist optimal für P, aber nicht unbedingt für P Strich.
Also wenn Sie jetzt statt X Strich X Stern schreiben, machen Sie es
vielleicht noch ein bisschen kleiner.
So, jetzt habe ich dieses Skalarprodukt da mal ein bisschen salopp
ausgeschrieben.
Und zwar, also ich habe da geschrieben, Summe der I aus X Stern, damit
meine ich die I, wo X Stern I gleich 1 ist.
Die anderen Summanden sind 0.
Und da steht also K mal Pi durch K abgerundet.
Und jetzt machen wir es noch kleiner, indem wir statt dem Abrunden Pi
durch K minus 1 schreiben.
Und dann bleibt übrig Summe der Pi minus Summe, so und so oft mal
immer der gleiche Summand K.
Summe der Pi für die I aus X Stern, das ist jetzt genau der optimale
Profit für das Originalproblem.
Das ist das P mal X Stern.
Und hinten ziehen wir ein paar mal K ab und machen es noch kleiner,
indem wir im Extremfall ganz extrem N malen.
Mehr Summanden können es nicht sein.
N mal K abziehen.
So, N mal K, das K war gewählt als Y mal P durch N, steht in der
ersten Zeile oben.
Das heißt, N mal K ist Y mal P. Und P ist der maximale Profit eines
Objekts, das wir da zur Verfügung haben.
Und wenn Sie sich erinnern, wir haben gesagt, naja OBDA, jedes Objekt
passt einzeln in den Rucksack.
Das heißt, der optimale Profit ist mindestens so groß wie der größte
Einzelprofit.
Das heißt, statt groß P können Sie jetzt ein bisschen mehr noch
abziehen, indem Sie sagen, naja, dann nehme ich halt das Optimum P mal
X Stern.
Ja, und dann sind wir fertig.
Und dass die Laufzeit polynomiell ist, das ist ganz banal.
Also, man muss halt das N mal P Strich Dach, also jetzt die Summe der
Pi Strich, das muss man abschätzen.
Und, naja, jedes Pi Strich ist kleiner gleich dem maximalen Pi Strich.
Und das maximale Pi Strich kriegen Sie, indem Sie das maximale P durch
K teilen.
Und wenn Sie jetzt dann für K noch Y mal P durch N da reinsetzen, dann
kriegt sich noch ein P. Und dann lassen wir auch das Abrunden weg,
machen es noch ein bisschen größer, dann steht da N hoch 3 mal 1 durch
Epsilon.
Was offensichtlich polynomiell in N und polynomiell in 1 durch Epsilon
ist.
Fertig.
Und das ist die letzte Folie, wenn ich mich... Nein, es gibt noch eine
Folie.
Also, das ist jetzt noch kubische Laufzeit und dann gibt es sehr viel
kompliziertere Algorithmen.
Also vollpolynomielle Approximationsschemata, da ist das hoch 3 weg.
Und die Praktiker haben auf die Folien von früheren Jahren
geschrieben, in der Praxis, man schafft immer, in Anführungszeichen,
fast Linearzeit, sozusagen.
Also, alles ist gut.
Jo.
Das war es zu dem Kapitel in der Vorlesung zu
Approximationsalgorithmen.
Und dann geht es jetzt weiter mit der Übung?
Okay, danke schön.
So, dann kommen wir zur Übung.
Wir haben die Übung diese Woche nach vorne verschoben, weil es
thematisch ein bisschen besser passt.
Und ab morgen wird dann Simon Gock mit der Vorlesung zu String
-Algorithmen, glaube ich, weitermachen.
Und danach geht es dann weiter mit geometrischen Algorithmen.
Gut, alles klar.
Und dann fangen wir mit der Übung an.
Zur Übung, letzten Donnerstag wurde die Lösung zum ersten Übungsblatt
veröffentlicht und morgen kommt dann das zweite Übungsblatt.
Wir machen also heute weiter mit Übungs-Approximationsalgorithmen.
Das ist ja gerade noch ganz frisch.
Also, Approximationsalgorithmen, was wollen wir nochmal machen?
Wir haben irgendwie schwierige Algorithmen, wie zum Beispiel aus der
Vorlesung das TSP-Problem, das Traveling Salesperson Problem.
Und das hat das Beste, was wir dafür kennen, hat exponentielle
Laufzeit.
Das heißt, es wird irgendwie, wenn wir da jetzt eine ausreichend große
Eingabe reinwerfen, dann wird das irgendwie niemals fertig.
Selbst mit Computern von zehn Jahren würde das, wenn wir ein groß
genuges Problem reinwerfen, wahrscheinlich niemals fertig exakt.
Das heißt, wir möchten irgendwie eine vernünftige Näherung finden, die
man aber vielleicht irgendwie in ein paar Sekunden oder einer halben
Stunde oder sowas berechnen kann.
Also, zum Beispiel irgendwie, wir könnten jetzt irgendwie für dieses
Problem hier unten haben wir Traveling Salesperson oder sowas
ähnliches.
Also Traveling Salesperson wollen wir ja in der Regel einen Kreis
finden mit minimaler Länge.
Das hier ist jetzt halt irgendwie nur ein Pfad, aber ist ähnlich.
Also unten rechts, das wäre irgendwie so das Beste, was man hier
erreichen könnte.
Wir laufen irgendwie so in Zig-Zag-Winkeln drumherum.
Und jetzt können wir uns irgendwie zwei Algorithmen forschen, die hier
was machen könnten.
Entweder irgendwie der unten links, der mal völlig wirr durch diesen
Grafen durchgeht.
Und wir finden halt sowas wie in der Mitte.
Also irgendwie die optimale Länge wäre 24 und der in der Mitte findet
irgendwie 8 plus 16 mal Wurzel 2.
Wurzel 2 ist irgendwie klein, das ist also irgendwie schon
einigermaßen nah an 24 dran.
Und solche in Anführungsstrichen guten Lösungen sind halt oft schon
genug für das, was wir brauchen.
Kommt auf die Anwendung an, aber oft ist es nun mal genug.
Aber was uns halt interessieren würde, ist ja wie gut sind wir denn
jetzt wirklich.
Also einfach nur zu sagen, ja das klingt gut, klingt als könntest du
vernünftige Lösungen berechnen, das reicht uns halt nicht.
Wir wollen etwas haben, wo wir wirklich garantieren können, das ist
irgendwie gut.
Und was wir dafür machen ist, wir definieren uns ein Gütemaß, den
Approximationsfaktor.
Wir haben also irgendwie einen Algorithmus ALG.
Und außerdem sagen wir, okay, es gibt irgendwie auch noch eine
optimale Lösung zu diesem Problem.
Also ALG ist ein Approximationsalgorithmus.
Und außerdem haben wir eine Bewertungsfunktion.
Das wäre bei Traveling Salesperson irgendwie die Länge dieses Kreises,
die wir finden.
Die nennen wir hier W.
Und jetzt teilen wir die Güte, die Kosten der Lösung, die unser
Algorithmus findet, durch die Kosten, die der optimale Algorithmus für
diese Instanz finden würde.
Und wenn wir das abschätzen können mit einem Faktor Rho, dann sagen
wir, unser Algorithmus hat einen Approximationsfaktor Rho.
Das muss für alle Eingaben gelten.
Es kann irgendwie Eingaben geben, für die unser Algorithmus optimale
Lösungen findet, aber sobald es eine gibt, wo er nicht optimal ist,
müssen wir es...
sagen wir, genau dieser Faktor ist unser Approximationsfaktor.
Ein Beispiel dafür wäre, unser Algorithmus schätzt aus welchem Grund
auch immer eine Strecke, die wir irgendwo finden in einem Graphen, ab
auf die nächsthöhere Zweierpotenz.
Warum auch immer er das tun sollte, vielleicht kann man das total
schnell machen.
Es braucht irgendwie weniger Speicherplatz.
Um die gesamte Länge abzuspeichern, brauchen wir viele Bits.
Wenn wir nur einen Logarithmus abspeichern, brauchen wir weniger Bits,
weil wir nur die Stelle speichern müssen, wo ein Bit eins gesetzt ist.
Formal ausgedrückt ist das zwei hoch aufgerundete Logarithmus von
Länge von x, wenn x unser Pfad ist.
Wir gehen davon aus, dass Opt der Algorithmus ist, der die korrekte
Distanz von x berechnet.
Und jetzt teilen wir das mal durcheinander.
B von Alt durch W von Opt ist gleich.
Unser Algorithmus bringt dieses zwei hoch aufgerundete Logbetrag von
x.
Opt findet Betrag von x, weil er optimal ist.
Wir machen mal dieses Aufrunden weg, damit kann man schlecht rechnen.
Wir sagen einfach, das Aufrunden ist schlimmstenfalls plus 1.
Also haben wir oben zwei hoch Logbetrag von x plus 1.
Jetzt ziehen wir uns diese plus 1 raus.
Wir haben zwei hoch Logbetrag von x mal 2.
Das heißt, das zwei hoch Logbetrag von x wird zu einem x.
Betrag von x mal 2 immer noch durch Betrag von x.
Das wird zu einer 2.
Das heißt, wir haben hier einen Approximationsfaktor von 2, was auch
irgendwie Sinn ergibt, weil wenn wir auf die nächste 2 Potenz
aufrunden, die ist maximal 2 entfernt.
Solche Algorithmen lassen sich in Klassen aufteilen.
Und da definieren wir uns hier jetzt drei Klassen.
Ich bin mir jetzt nicht sicher, ob APX, ob das so explizit in der
Vorlesung genannt wurde, PETAS und FPETAS haben wir gerade schon
gesehen.
Also wir sagen, wir haben eine Laufzeit, t, und die hängt ab von n,
also unserer Eingabegröße, wie bei jedem Algorithmus in der Regel, und
einem Epsilon, einer zusätzlichen Eingabe Epsilon.
Und wir haben einen Approximationsfaktor, der ist auch abhängig von n
und wieder unserem Epsilon.
Und jetzt könnten wir einen Algorithmus haben, der schafft es, dass
wir für jedes n immer ein konstantes rho haben, also zum Beispiel 2.
Wie wir in dem Beispiel eben gesehen haben, da war rho gleich 2.
Und wir wollen aber, weil sonst machen Approximationsalgorithmen oft
keinen Sinn, wir wollen da irgendwie Polynomialzeit haben.
Weil wenn wir irgendwie mehr als Polynomialzeit erlauben, dann kommen
wir meistens irgendwie auch wahrscheinlich schon an eine optimale
Lösung.
Gut, ein Beispiel dafür ist hier unten die erste Zeile.
Wir haben also eine Zeit, die ist polynomiell in n, zum Beispiel n
hoch 1 durch Epsilon.
Und wir haben einen konstanten Approximationsfaktor von 2.
Das nächst einschränkendere, was wir uns dann definieren, sind die
Peters.
Das sind Algorithmen, die laufen polynomiell in der Eingabegröße n.
Und diesmal können wir aber beliebig nah an unsere optimale Lösung
rankommen mit unserem Parameter Epsilon.
Also rho ist irgendwie 1 plus minus Epsilon und Epsilon ist zwischen 0
und 1.
Also wir können da irgendwie auf 5 Prozent oder auf 1 Prozent oder auf
0,01 Prozent, wir können da beliebig nah rankommen an die optimale
Lösung.
Könnten dafür aber vielleicht ein bisschen mit Laufzeit bezahlen.
Zum Beispiel diese zweite Zeile in den Beispielen hier.
Da haben wir jetzt immer noch Laufzeit n hoch 1 durch Epsilon.
Also wir zahlen irgendwie für größere Epsilons, für kleinere Epsilons,
Entschuldigung, zahlen wir irgendwie Laufzeit.
Aber dafür kommen wir auch näher an unsere optimale Lösung ran.
Also auf 1 minus Epsilon.
Also Minus macht natürlich nur Sinn für Maximierungsprobleme.
Also für Minimierungsprobleme ist es irgendwie unrealistisch, dass wir
kleiner werden als die optimale Lösung.
Und das nächste wären dann F-Peters.
Die sind fully polynomial, also sie laufen auch noch polynomial in
unserem 1 durch Epsilon.
Also Laufzeitpolynomial in n und 1 durch Epsilon.
Und wir kommen auch wieder beliebig nah bis auf das Epsilon an die
optimale Lösung dran.
Jetzt darf also 1 durch Epsilon nicht mehr in den Exponenten stehen,
sondern wir haben jetzt hier zum Beispiel 1 durch Epsilon mal n als
Laufzeit.
Und unser Approximationsfaktor ist zum Beispiel 1 plus 2 Epsilon.
Die 2 macht hier gar nichts aus.
Also wir können irgendwie, wenn wir eine 5% Annäherung haben wollen,
dann setzen wir für Epsilon halt einfach 2,5% ein.
Und dann kommt bei unserem Roh wieder 1 plus 5% raus.
Das sind alles hierarchische Strukturen.
Wir haben erstmal dieses APX, also die Algorithmen, die approximieren.
Also mit einem konstanten Faktor.
Was wir da noch machen können ist, wir können unseren
Approximationsfaktor klein drücken.
Das ist also irgendwie eine stärkere Annahme als einfach nur ein
konstanter Approximationsfaktor.
Und als nächstes haben wir, wir können den Approximationsfaktor klein
drücken.
Und wir sind dabei auch noch schnell.
Das sind irgendwie alle so Teilmengen voneinander.
Wir gucken uns jetzt nochmal ein Beispiel an aus der Vorlesung, weil
dazu scheinbar nach der Vorlesung am letzten Montag eine Frage aufkam.
Nochmal zur Wiederholung.
Also es geht um dieses Scheduling-Problem aus der Vorlesung.
Wir haben also irgendwie N Jobs und N Maschinen.
Diese Maschinen können irgendwie parallel Sachen ausführen.
Diese Jobs sind völlig unabhängig voneinander.
Sie können hintereinander laufen, welche Reihenfolge sie auch wollen.
Und auch gleichzeitig, wir wissen, wie lange das Ganze läuft.
Und außerdem nehmen wir einen Offline-Algorithmus im Vergleich zu
Online -Algorithmen, die später, glaube ich, noch in der Vorlesung
kommen werden.
Und wir sagen jetzt, jeder dieser Jobs hat eine Laufzeit.
tj gibt die Laufzeit von Job j an.
Und für den Algorithmus gleich definieren wir uns noch so ein x von j,
also x an der Stelle j, das ist eine Array, und da steht irgendwie
drin, die Maschine, auf der der Job j ausgeführt wird.
Also xj ist vielleicht Maschine 2.
Job j wird auf Maschine 2 ausgeführt.
Was wir dann auch noch brauchen, ist, wie ausgelastet ist gerade eine
Maschine.
Das ist irgendwie formal hier die Summe über dieses Array x, und zwar
alle Stellen, an denen die entsprechende Stelle auf diese Maschine
gesetzt ist.
Also Maschine i hat eine Auslastung von der Summe der Laufzeiten der
Jobs, die auf dieser Maschine geschedult sind.
Und was wir jetzt minimieren möchten, ist das maximale L von i.
Das heißt, wir sagen, unser gesamter Schedule ist fertig, wenn auch
die letzte Maschine alle ihre Jobs abgearbeitet hat.
Und das ist unsere Zielfunktion.
Die wollen wir minimieren.
Wir wollen so schnell möglich sein wie möglich.
Und das Ganze nennen wir MakeSpan.
Das hier ist wahrscheinlich ein bisschen anders aufgeschrieben als in
der Vorlesung.
Das ist der Algorithmus, wie in der Vorlesung dran kam.
Wir nehmen uns erstmal eine Menge j.
Diese Menge j soll einfach alle Jobs repräsentieren.
Dann unser Array l, wo also die Auslastung der Maschinen drin stehen.
Da setzen wir alles auf 0.
Und dann loopen wir durch diese Menge j, entfernen uns immer irgendein
Element aus dieser Menge, suchen uns die Maschine, die zurzeit die
geringste Auslastung hat, und weisen diesen Job an diese Maschine zu.
Und dann müssen wir irgendwie noch hochrechnen.
Ja, okay, diese Maschine ist jetzt irgendwie stärker ausgelastet.
Und nach der Vorlesung kam jetzt irgendwie die Frage, ja, was ist
denn, wenn wir diese Jobs einfach mal der Größe nach sortieren?
Weil das Beispiel, was man sich hier irgendwie angucken konnte, wann
das irgendwie sehr schlecht funktioniert, war irgendwie sowas, wir
haben erst einen Haufen kleine Jobs und dann am Ende kommt ein großer
Job.
Und unglücklich wie wir sind, ist das nun mal der Job, den unser
Algorithmus als letztes auswählt.
Dann hatten wir irgendwie alles bisher perfekt balanciert vielleicht,
weil unser Algorithmus das irgendwie schafft.
Und am Ende kommt ein großer Job und der macht uns alles kaputt.
Alle Maschinen sind fertig außer einer und der muss noch diesen
letzten Job bearbeiten.
Und wie könnte man das fixen?
Naja, dieses eine spezielle Beispiel könnte man irgendwie dadurch
fixen, indem wir einfach mal den längsten Job zuerst ausführen.
Und dann müssen wir nur noch diese ganzen kleinen Jobs einsortieren,
sodass die noch vernünftig funktionieren.
Und die Antwort auf was dann passiert ist, das funktioniert ein
bisschen besser.
Optimal ist es nicht, aber es ist immerhin eine
Vierdrittelapproximation.
Also geändert hat sich jetzt in diesem Algorithmus nur diese eine
Zeile unter dem While.
Wir wählen uns jetzt nicht mehr ein beliebiges Element aus unseren
Jobs, sondern gerade den mit der höchsten Ausführungszeit.
Und jetzt müssen wir uns halt mal angucken, wie können wir das jetzt
abschätzen, was passiert hier.
Und wir teilen das uns ein bisschen auf in zwei Fälle.
Und zwar einmal, der erste Fall ist, dass der kleinste Job ziemlich
schnell ist.
Wir sortieren uns also unsere Jobs in dieser Reihenfolge, in der wir
sie in unserem Algorithmus brauchen.
Der größte Job zuerst, dann der zweitgrößte und am Ende Tn ist der
kleinste Job.
Und jetzt müssen wir erst mal eine Annahme treffen.
Und zwar sagen wir unbeschränkter Allgemeinheit gilt, dass der Job N,
den wir hier an die Stelle N gesetzt haben, wird als letztes fertig.
Und warum können wir das annehmen?
Wir können sonst einfach diesen Job weglassen.
Was passiert dann mit unseren beiden Lösungen, die wir hier
betrachten?
Also die optimale Lösung könnte dann irgendwie besser werden,
offensichtlich.
Wir haben einen Job weniger, der eine optimale Lösung hat, also besser
werden.
Aber unser Algorithmus, wenn wir angucken, ich habe ihn hier LPT
genannt, LPT für Largest Processing Time.
Das ist auch das, worüber man ihn findet, wenn man ihn irgendwo mal
sucht.
Dann, der Schedule, den LPT berechnet, der bleibt genau gleich.
Ja, weil wenn der kleinste Job ist, der der als letztes geschedult
wird.
Das heißt, wenn er nicht als letztes fertig wird, wenn wir diesen Job
einfach weglassen, dann werden alle Jobs, die vorher dran kamen, immer
noch genau gleich geschedult.
Weil die hatten ja auch, als sie so geschedult wurden, noch gar keine
Ahnung, dass der Job danach kommt.
So ein bisschen zur Illustration, mal dieses Bild da unten, ja.
Dieser Job mit der Länge 2 ist irgendwie der, der am kürzesten
braucht, aber wird nicht als letztes fertig.
Und was wir jetzt machen werden, für unseren Beweis, wir werden ihn
einfach mal rausschmeißen.
Und wir sehen irgendwie, ja, der Schedule, den LPT berechnet, der
bleibt irgendwie gleich.
Und jetzt ist 4, der da als letztes fertig wird und das ist auch der
mit der kürzesten Ausführungszeit.
Was wir jetzt zeigen werden, ist, wenn Job N als letztes fertig wird,
dann ist LPT eine Vierdrittelapproximation.
Ansonsten, ja was kann ansonsten passieren, wenn jetzt irgendwie noch
ein Job dazukommt, ein kleinerer Job, der nicht als letztes fertig
wird, dann bleibt der Max-Band von LPT gleich.
Also dieses W von LPT bleibt immer noch genau das gleiche.
Aber W von OPT könnte nur noch schlechter werden.
Das heißt, wir konnten irgendwie diese Vierdrittel-Abschätzung machen
mit einer optimalen Lösung, die besser war.
Also wird diese Abschätzung wohl auch immer noch gelten, wenn unsere
optimale Lösung schlechter ist.
Weil unsere Lösung von LPT ist immer noch genau die gleiche.
Also hat genau das gleiche Gewicht, genau die gleichen Kosten.
Gut, was können wir jetzt also tun?
Naja, wir können sagen, der Max-Band von LPT ist irgendwie die Zeit,
zu der Job N gestartet wird, plus die Laufzeit von Job N.
Und das schätzen wir jetzt ab mit dieser Abschätzung, die müsste auch
für die Zwei-Approximation aus der Vorlesung wahrscheinlich schon
gemacht worden sein, so ähnlich.
Dieses 1 durch M mal Summe über die TI.
Wenn wir jetzt einfach mal dieses I ungleich N weglassen, das ist
irgendwie der Fall, alle Jobs sind perfekt aufgeteilt.
Also jede Maschine hat genau gleich viel Arbeit.
Das heißt, das ist irgendwie der späteste Zeitpunkt, zu dem irgendwie
diese Maschine, auf der der letzte Job gestartet wird, fertig werden
kann.
Weil unser Algorithmus wird wahrscheinlich irgendwie eine Imbalance
haben, also irgendwie wird eine Maschine früher fertig und eine
Maschine später.
Das heißt, die früheste muss aber früher fertig werden, als der
Zeitpunkt, wenn alles gleich verteilt wäre.
Gut, das heißt, das können wir irgendwie damit abschätzen und außerdem
schmeißen wir auch noch diesen Job N raus, weil der ist ja noch
überhaupt nicht geschedult.
Gut, und darauf addieren müssen wir aber noch die Laufzeit davon.
So, unser optimaler Algorithmus kann natürlich auch nicht besser sein,
als alles perfekt aufzuteilen.
Das heißt, wir schätzen diese Summe mit dem Makespan vom optimalen
Algorithmus ab.
Dann haben wir also optimaler Algorithmus plus die Laufzeit vom
letzten Job.
Und jetzt kommt nämlich der Punkt, wo wir unsere Fallunterscheidung
machen.
Wir sagen jetzt, okay, wenn unser letzter Job kürzer dauert als die
optimale Lösung für unser gesamten Schedule durch drei, dann ist das
halt irgendwie eine Vierdrittelapproximation offensichtlich.
Also einmal optimale Lösung plus ein Drittel mal optimale Lösung ist
Vierdrittel.
Und jetzt kommt der interessantere Teil.
Und zwar, was ist denn jetzt, wenn unser Job, wenn der kürzeste Job,
den wir haben, länger braucht als WvOp durch drei.
Das bedeutet übrigens insbesondere, alle Jobs brauchen länger als Op
durch drei.
Und ich entschuldige mich, da ist ein kleiner Fehler, das werde ich
gleich noch korrigieren.
Das sollte T von I größer als WvOp durch drei sein, nicht größer
gleich.
Weil den Gleichfall, den haben wir gerade schon behandelt, für den
Fall, dass der kürzeste Job kurz dauert.
So und was wir jetzt sogar zeigen ist, naja, für diesen Fall ist LPT
sogar optimal.
Also die Lösung, die LPT findet, besser geht's nicht.
Und wir machen das, indem wir uns jetzt einfach erstmal nur angucken,
wie sieht eine möglich optimale Lösung aus.
Und wir ignorieren jetzt erstmal für den Moment komplett, was unser
Algorithmus tut.
Wir werden hinterher gucken, wir werden hinterher feststellen, okay,
LPT tut irgendwie das gleiche.
Das erste, was wir mal feststellen können, ist, jede Maschine arbeitet
maximal zwei Jobs ab.
Weil wenn sie drei abarbeiten würde, dann hätte sie irgendwie drei
Jobs, die alle mehr als ein Drittel mal die optimale Lösung brauchen.
Das geht nicht.
Dann haben wir irgendwie was Größeres als die optimale Lösung.
Gut, wir nennen diese beiden Jobs für Maschine I, nennen wir diese
beiden Jobs I1 und I2.
Und wir sortieren unsere Maschinen jetzt so, dass die erste Maschine
den längsten Job kriegt, die zweite Maschine den zweitlängsten Job und
so weiter.
In dieser Reihenfolge sortieren wir unsere Maschinen.
Und wir können jetzt sagen, es gibt jetzt auf jeden Fall eine optimale
Lösung, in der die zweiten Jobs, die die Maschinen kriegen, dann genau
andersrum sortiert sind.
Also dann kriegt irgendwie die unterste Maschine, also wir haben die
ersten M-Jobs vergeben, die längsten M-Jobs haben wir vergeben.
Und jetzt kriegt die letzte Maschine in unserer Reihenfolge, kriegt
von den verbleibenden Jobs den längsten.
Und darüber den zweitlängsten und so weiter.
Und warum können wir das machen?
Naja, wenn wir irgendwie ein Schedule finden, in dem das nicht der
Fall ist, dann können wir das einfach vertauschen.
Hier unten ist das mal illustriert.
Irgendwie diese 45 und 50 da, die sind irgendwie nicht in der
Reihenfolge, wie wir es oben haben wollen.
Aber wenn wir sie vertauschen, dann bleibt unser Makespan immer noch
genau gleich.
Weil wir halt irgendwie etwas...
Ja, wir haben irgendwie etwas einen längeren Job an einen anderen
schon langen Job drangehangen.
Das wird auf jeden Fall nur besser, wenn wir einfach diesen langen Job
an einen kürzeren Job dranhängen.
Also die 50 an die 70 hängen und stattdessen halt die 45 an die 75.
Das kann nur besser werden.
Also die können wir auf jeden Fall vertauschen.
Das heißt, wir wissen jetzt, dass es einen optimalen Schedule gibt,
der irgendwie so erstmal alle Jobs der Reihenfolge, also von lang nach
kurz, irgendwie erstmal von oben nach unten an die Maschinen zuweist
und dann wieder hoch geht, die verbleibenden Jobs nach oben zuweist.
Was wir jetzt sagen wollen ist, okay, LPT berechnet den gleichen
Schedule.
Genau diesen.
Wir betrachten jetzt nur den Fall, wir haben mehr Jobs als Maschinen,
weil der andere Fall ist langweilig.
Da kriegt jede Maschine einen Job.
Fertig.
Und die erste Feststellung ist erstmal, wenn LPT jeder Maschinen
maximal zwei Jobs zuweist, dann ist das genau der, den wir gerade
diskutiert haben.
Und zwar warum?
Naja, also die ersten Jobs sind wieder klar.
Wir weisen irgendwie erstmal, bis wir jeder Maschine einen Job
zugewiesen haben, weisen wir nur mal jeder Maschine einen Job zu.
Und die zweiten Jobs, naja, also der Job, der die Maschine die
geringste Auslastung hat, wenn alle Maschinen schon voll sind, der war
als letztes den ersten Job gegeben haben.
Und da wir jetzt davon ausgehen, wir haben jetzt irgendwie den Fall,
in dem LPT jeder Maschine maximal zwei Jobs zuweist, wissen wir auch,
dass dieser zweite Job nicht fertig werden wird, bevor einer der
anderen Jobs fertig ist.
Bevor eine der Maschinen mit nur einem Job fertig wird.
Weil sonst würden wir ja einen dritten Job zuweisen, aber den Fall
betrachten wir gerade gar nicht.
Das heißt, wir wissen jetzt irgendwie, das wird genau der gleiche
Schedule sein, wenn LPT maximal zwei Jobs zuweist.
Das könnte es ja irgendwie aber sein.
Aber kann nicht LPT vielleicht einer Maschine drei Jobs zuweisen?
Weil das wäre ja doof.
Weil drei Jobs können nicht die optimale Lösung ergeben.
Und was wir uns dafür angucken ist, also erstmal, wir wissen, es gibt
maximal doppelt so viele Jobs wie Maschinen, weil sonst müsste eine
Maschine drei Jobs haben.
Das heißt, die optimale Lösung ist so nicht möglich.
Das heißt insbesondere, es gibt in LPT...
Es gibt eine Maschine bei LPT, die nur einen Job hat.
Die aber in Opt zwei hat.
Weil, naja, irgendwo muss in der optimalen Lösung dieser dritte Job,
den wir an eine Maschine zuweisen, dahin sein.
Wir nennen diesen Job K.
Diesen Job, der alleine auf einer Maschine ist.
Nennen wir K.
So, dieser Job dauert also länger als zwei andere Jobs, weil sonst
hätten wir ja...
Sonst hätten wir schon einen Job an die Maschine zugewiesen, die Job K
abarbeitet.
Wir gehen ja davon aus, dass LPT weist einen Job an die Maschine zu,
die schon zwei Jobs hat.
Das heißt insbesondere, es muss einen Job geben, der länger ist als
irgendwelche zwei Jobs, die wir schon haben.
Gut, das bedeutet aber insbesondere auch, dieser Job K hat eine
Laufzeit, die länger ist als zweimal die optimale Lösung durch drei.
Das heißt, es ist absolut unmöglich, dass diese Maschine noch einen
weiteren Job abarbeitet.
Aber wir sind gerade davon ausgegangen, dass die optimale Lösung das
tut.
Also das geht nicht.
Das heißt, wir haben Widerspruch dazu gefunden, dass unser Algorithmus
irgendeiner Maschine drei Jobs zuweist.
Und damit haben wir fertig gezeigt, LPT findet eine optimale Lösung
für diesen Fall, dass der letzte Job oder dass alle Jobs länger
brauchen als die optimale Lösung durch drei.
Gut, dann gibt es erstmal zu dem Scheduling Zeug Fragen.
Das müssen wir nämlich weitermachen mit Minimum Metric TSP.
Da finden wir jetzt auch noch eine bessere Approximation als aus der
Vorlesung gegeben.
Ja, wir haben irgendwie eine Menge an Punkten und die liegen in einer
Ebene.
Diese Punkte sind alle miteinander verbunden und wir gehen davon aus,
dass unser Graph die Dreiecksumgleichung erfüllt.
Das heißt, Umwege lohnen sich nicht.
Also wir können...
Der direkte Weg von A nach B ist immer mindestens genauso kurz wie von
A nach C und von C wieder nach B.
Das kann sich nicht lohnen.
Und was wir jetzt finden wollen, ist ein Kreis minimaler Länge, der
alle Punkte abläuft.
Die Zweidrittel-Approximation dafür sieht jetzt wie folgt aus.
Wir haben einen Graphen, der vollständig ist, der ungerichtet ist und
erfüllt unsere Dreiecksumgleichung.
Zum Beispiel den hier.
Diese grünen Kanten haben Länge 2, die grauen haben Länge 1.
Und wenn man sich mal anguckt, überspringen die grünen immer einen
Knoten.
Also die Dreiecksumgleichung ist hier erfüllt.
Der erste Schritt unseres Algorithmus ist, wir bestimmen einen MST.
Also einen minimalen Spannbaum in G.
Das könnte zum Beispiel dieser rote sein.
Und suchen uns jetzt die Knoten raus in T, die ungeraden Grad haben.
Also nicht im Ursprungsgrafen, sondern die in T ungeraden Grad haben.
Das sind jetzt hier die Knoten, die wir hier umgesselt haben.
Das ist die Menge U.
Das sind genau die Knoten, die in unserem Beispiel hier Grad 3 und
Grad 1 haben.
Und finden jetzt ein minimales perfektes Matching auf dieser Menge U
mit allen Kanten.
Nicht nur mit den Baumkanten.
Minimales perfektes Matching, was bedeutet das?
Also ein Matching ist eine Menge an Kanten, sodass kein Knoten zu mehr
als zwei Kanten in diesem Matching-Inzident ist.
Minimal bedeutet, wir möchten gerne ein so geringes Gewicht wie
möglich dabei benutzen.
Und perfekt bedeutet, jeder Knoten muss gematcht sein.
Und zum Beispiel wäre das hier das blau angezeichnete Matching M.
Das wäre in unserem Beispiel ein minimales perfektes Matching auf der
Knotenmenge U.
Und diese Matching-Kanten fügen wir jetzt mal zu unserem minimalen
Spannraum hinzu und nennen jetzt diesen neuen Graphen T'.
Und jetzt bestimmen wir einen Euler-Kreis darauf.
Ein Euler-Kreis ist ein Kreis in einem Graphen, der jede Kante genau
einmal benutzt.
Das heißt, wir können einfach alle diese Kanten, die wir da in T'
hatten, reinnehmen und haben einen Euler-Kreis.
Wenn wir sie in der richtigen Reihenfolge ablaufen.
Und was wir jetzt noch als letzten Schritt machen, ist das Ganze in
einen Hamilton-Kreis umwandeln.
Ein Hamilton-Kreis ist ein Kreis in einem Graphen, der jeden Knoten
einmal besucht.
Und was wir da zu tun ist, wir laufen unseren Euler-Kreis ab und jedes
Mal, wenn wir an einem Knoten vorbeikommen, den wir schon mal gesehen
haben, dann überspringen wir den einfach.
Und das wird ja schon mal intuitiv unsere Lösung auf keinen Fall
verschlechtern, weil wir gehen ja davon aus, dass Umwege sich gar
nicht lohnen.
Also dieser Weg, den wir hier gemacht haben, wir sind von 1 nach 2
nach 1 nach 3 gelaufen, aber die Dreiecksungleichung sagt uns ja, wir
wissen ja, dass wir einfach, nachdem wir bei 2 waren, direkt zu 3
laufen können.
Das ist definitiv mal schneller als, oder mindestens genauso schnell,
wie erst nach 1 und dann wieder nach 3 zu laufen.
Und als Anmerkung hierzu, also dieser Algorithmus, das geht irgendwie
alles ziemlich schnell, außer das minimalperfekte Matching, das kann
man in kubischer Laufzeit finden.
Wir haben jetzt irgendwie ein Algorithmus in kubischer Laufzeit und
wollen jetzt mal gucken, wie gut ist der denn jetzt.
Achso, genau, und das hat irgendwie wirklich eine 6 hier in diesem
Beispiel.
Gut, wir haben eine Tour gefunden der Länge 6.
Gut, was für Abschätzungen können wir hiermit machen?
Unser Hamilton-Kreis, also der Kreis, der alle Knoten genau einmal
benutzt.
Die Länge von diesem Hamilton-Kreis ist auf jeden Fall mal kleiner
gleich die Länge von unserem Euler-Kreis.
Genau wegen dem Argument eben.
Knoten überspringen wird auf jeden Fall nichts verschlechtern, weil
Abkürzungen sind immer besser als den Umweg zu gehen.
Gut, dieser Euler-Kreis...
Dieser Euler-Kreis waren genau die Kanten, die wir in T' drin hatten.
Da haben wir einfach genau die Kanten genommen, d.h.
die sind gleich die Gewichte davon.
Dieses T', also Gewicht von einem minimalen Spannbaum, plus dieses
Matching, was wir gefunden haben.
Und jetzt können wir uns irgendwie überlegen, naja, so ein minimaler
Spannbaum und Travelling Salesman ist irgendwie ziemlich ähnlich.
Außer, dass der minimale Spannbaum halt ein Kreis, äh, ein Baum ist
und Travelling Salesman ein Kreis.
Wenn wir aus einer Travelling Salesman-Route einfach eine Kante
rausnehmen, ist das auf jeden Fall ein Spannbaum.
Ja, da wird jeder Knoten genau einmal besucht und es ist irgendwie ein
Baum.
Das heißt also, eine TSP-Route kann nicht besser sein als ein MST.
Kann gar nicht kleiner sein.
Das heißt, wir können dieses W von T durch W von Opt abschätzen.
Und womit wir jetzt verbleiben, ist irgendwie noch dieses W von M.
Damit müssen wir jetzt noch irgendwas machen.
So, das wollen wir jetzt also bestimmen.
Und jetzt holen wir uns erstmal wieder diese Knotenmenge U her.
Also irgendwie, das M war ja irgendwas mit dieser Knotenmenge U.
Das war so ein minimales, perfektes Matching auf der Knotenmenge U.
Die holen wir uns erstmal her und definieren uns darauf einen neuen
Hamilton -Kreis-HK-Strich auf genau diesen Knoten.
Und wie wir den konstruieren, ist...
Also das ist ein Pfad, den müssen wir uns konstruieren für den Beweis.
Den haben wir uns wahrscheinlich nie wirklich konstruiert.
Aber wir erzeugen uns den, indem wir die optimale Lösung nehmen für
das Traveling-Salesman-Problem.
Und einfach alle Knoten überspringen, die nicht in U sind.
Also irgendwie oben und links die Knoten, die sind nicht in U.
So, die überspringen wir einfach und verbinden die Knoten in U einfach
direkt.
Jetzt definieren wir uns hier drauf alternierende perfekte Matchings.
Das bedeutet, jeder Knoten muss genau einmal gematcht werden.
Wir erwarten jetzt hier aber nicht mehr, dass sie minimal sind.
Das geht im Allgemeinen nicht.
Alternieren bedeutet irgendwie einmal die erste, die dritte, die
fünfte und so weiter Kante nehmen...
und dann einmal noch die zweite, die vierte, die sechste und so weiter
Kante.
Also zum Beispiel hier Matching M1 und das ist Matching M2.
Das werden wir wahrscheinlich jetzt gerade erstmal nicht machen.
Das funktioniert halt, und auch vorher, das minimale perfekte
Matching.
Das funktioniert halt, weil wir in unserer Knotenmenge U eine gerade
Anzahl Knoten haben.
Das wird wahrscheinlich aufs Übungsblatt kommen, aber es ist ziemlich
leicht zu sehen, dass es eine gerade Anzahl an Knoten ist.
So, was können wir jetzt abschätzen?
Unser Matching, was wir gefunden haben, das M, das war ein minimales
perfektes Matching auf unserer Knotenmenge U.
M1 und M2 sind irgendwelche Matchings auf unserer Knotenmenge U.
Das heißt, die Lösungsqualität von M ist kleiner gleich der von diesen
beiden anderen Matchings, die wir haben, weil M minimal war.
Gut, jetzt addieren wir die beiden also, M1 und M2, und können das
abschätzen mit zweimal der Qualität von unserem Matching M.
M1 und M2 ergeben zusammen genau unseren Hamilton-Kreis HK'.
Was wir jetzt sagen können, wir haben HK' noch mal konstruiert, indem
wir unsere optimale Lösung genommen haben und Knoten überspringen.
Knoten überspringen, der Hexungleichung sagt uns, das kann nur besser
werden.
Das heißt, wir wissen auch, W von HK' ist kleiner gleich W von der
optimalen Lösung.
Und was haben wir dann?
Wir teilen nochmal durch zwei.
Wir haben zweimal W von M, das teilen wir durch zwei, dann haben wir
also W von OPT durch zwei.
Oben war W von OPT plus W von M, wir haben also dreihalbe W von OPT
raus.
Wir haben also eine dreihalbe Approximation für Minimum Metric TSP,
was besser ist als die zwei Approximation aus der Vorlesung.
Und jetzt irgendwie die Frage, die wir jetzt heute glaube ich nicht
mehr schaffen, wenn ich das richtig in Erinnerung habe, was ich noch
vorhabe.
Wir müssen wissen, dass es immer eine gerade Anzahl an Knoten in U
drin ist.
Das ist relativ simpel.
Man guckt sich irgendwie an, wie viele Knoten in einem Graphen können
denn überhaupt ungeraden Grad haben.
Und das findet man heraus, dass es eine gerade Anzahl an Knoten sind.
Für das, was wir gleich machen, definiere ich mir irgendwie meinen
Approximationsfaktor ein bisschen um.
Sieht sehr ähnlich aus, ist im Grunde genommen die alte Definition,
nur dass wir mal W von OPT von I gemacht haben, werden wir gleich
benötigen, weil wir gleich eine optimale Lösung der Größe 0 haben und
sonst müssen wir unbedingt 0 teilen.
Aber ansonsten ist das das Gleiche.
Achso, gab es Fragen hierzu?
Alles klar, und zwar gucken wir uns das Problem an Graph
-Partitionierung und zwar perfekt balanciert.
Erstmal, was ist Graph-Partitionierung?
Wir haben einen Graphen und wir möchten uns die Knoten aufteilen in
Blöcke V1 bis Vk.
Und zwar so, dass die Vereinigung dieser Blöcke genau unsere
Knotenmenge ergibt und außerdem darf kein Knoten in zwei von diesen
Mengen drin sein, also wir müssen disjunkt sein.
Also irgendwie da unten haben wir so einen Graphen und diese blau
eingezeichneten Grenzen ergeben so eine Partitionierung, also jeder
Knoten ist in genau einem dieser Blöcke drin.
Und was wir außerdem fordern, ist, dass dieser Punkt perfekt
balanciert.
Wir fordern nämlich, dass diese Mengen alle genau gleich groß sind.
Also die müssen alle genau...
Ah, da ist ein kleiner Fehler, da sollten Betragsstriche um die
einzelnen Mengen sein.
Die Mengen müssen alle genau gleich groß sein.
Unsere Optimierungsfunktionen hierbei sind die Kanten, die über
Grenzen hinauslaufen.
Also Kanten, die zwischen zwei Knoten verlaufen, die nicht in der
gleichen Teilmenge von Knoten drin sind.
Das sind in diesem Bild da unten die roten Kanten, also alle Kanten,
die die blaue Linie kreuzen.
Das zu minimieren ist np.hard.
Und wir werden jetzt zeigen, dass das auch nicht in Polynomialzeiten
mit konstanten Faktoren approximierbar ist.
Und das machen wir, indem wir eine Reduktion von 3-Partition machen.
3-Partition ist dieses Problem.
Wir haben 3k Zahlen gegeben, n gleich 3k Zahlen, a1 bis an, und
zusätzlich noch einen Wert s.
Und wir haben dann irgendwie so ein Constraint, also irgendwie ai ist
größer als s viertel und kleiner als s halbe.
Das braucht man irgendwie für dieses Problem.
Wir wissen außerdem, die addieren sich insgesamt zu k mal s auf.
Und unser Problem, das Entscheidungsproblem, was wir hier jetzt lösen
müssen ist, können wir diese Zahlen a1 bis an so in Dreiergruppen
aufteilen, dass jede dieser Dreiergruppen sich zu s aufaddiert.
Also wir müssen k Dreiergruppen finden, die sich alle zu s
aufaddieren.
Und das Ganze ist streng np-vollständig.
Und was heißt streng?
Das ist selbst noch dann np-vollständig, wenn diese Zahlen a1 bis an
polynomial in n beschränkt sind.
Das brauchen wir gleich für unsere Reduktion, ansonsten ist nämlich
unsere Reduktion nicht von Polynomialzeit.
Wie sieht die Reduktion aus?
Geben wir eine Instanz von 3 Partition, wobei unsere Zahlen alle
polynomial in n beschränkt sind, das ist immer noch np-vollständig,
wie gerade gesagt, konstruieren wir uns jetzt einen Graphen G.
Folgendermaßen, für jede dieser Zahlen fügen wir einfach eine Clique
ein.
Und zwar der Größe genau dieser Zahl.
Also zum Beispiel ai ist jetzt hier in diesem Beispiel scheinbar 5.
Und das heißt wir fügen eine Clique der Größe 5 ein.
Eine Clique waren Knoten, die alle miteinander verbunden sind, also 5
Knoten, die alle miteinander verbunden sind.
Und für a2 und a3 usw.
machen wir es genau gleich.
Und zwischen diesen Cliquen laufen nirgendwo Kanten.
Und das ist jetzt der Punkt, weshalb wir brauchten, dass diese Zahlen
polynomial beschränkt sind.
Weil wenn sie es nicht wären, dann hätten wir einen Graphen, der nicht
polynomial in unserer Eingabegröße beschränkt ist.
Das heißt, unsere Reduktion würde nicht mehr in Polynomialzeit laufen.
Und wenn die Reduktion nicht in Polynomialzeit läuft, dann ist
irgendwie eh alles verloren.
Dann ist dieses ganze Schema von Reduktionen für irgendwelche NP
-Vollständigkeitsbeweise und sowas, das ist ja sehr ähnlich dazu, ist
dann alles hinweg.
Also das muss in Polynomialzeit laufen, die Reduktion.
Gut, aber das haben wir hier gegeben, weil wir polynomial viele Knoten
einfügen mussten.
Die Anzahl Kanten in einem Graphen sind eh polynomial beschränkt in
Anzahl Knoten.
Nämlich n².
Also ist auf jeden Fall eine Polynomialzeit-Reduktion.
Und was wir jetzt feststellen können ist, wenn unsere 3-Partition
-Instanz jetzt lösbar ist, dann finden wir auch eine K-Partition, also
eine, soll man vielleicht ein bisschen umformulieren, also eine
perfekt balancierte Partition in K-Blöcke mit Schnitt 0.
Weil das bedeutet, dass wir unsere Zahlen alle so aufteilen können,
dass jeder Block genau gleich groß ist.
Nämlich S aus unserem 3-Partition-Problem.
Und es laufen keine Kanten dazwischen.
Das heißt, wir mussten keine unserer Zahlen, unserer AI irgendwie
aufsplitten.
Wenn es allerdings keine Lösung gibt, das heißt, wir können unsere
Zahlen nicht in Dreierblöcke aufteilen, sodass jeder dieser
Dreierblöcke irgendwie S ergibt.
Und dann muss auch unsere perfekte K-Partition irgendwie mindestens
eine Kante schneiden.
Andernfalls könnten wir daraus ja wieder unsere Lösung für 3-Partition
formulieren.
Ja gut, das heißt, unsere optimale Lösung ist also 0, wenn es klappt.
Naja, und irgendwie in Approximations... wenn ich irgendwas
multipliziere mit 0, dann ist das halt immer noch 0.
Also muss mein Approximationsalgorithmus auch einen Schnitt der Größe
0 finden.
Ja gut, aber 3-Partition ist NP-vollständig.
Das heißt, wir hätten einen Polemialzeitalgorithmus, der einen Schnitt
der Größe 0 findet.
Ein Schnitt der Größe 0 ist die optimale Lösung.
Wir hätten damit 3-Partition gelöst.
Das funktioniert also nicht.
Genau, und damit wären wir am Ende.
Nächste Woche geht es in der Vorlesung mit String-Algorithmen weiter.
Die nächsten zwei Wochen wird die Übung, meinen Kollegen Jaroslav
Achremtze, falten.
Wir sehen uns dann in drei Wochen wieder.
Vielen Dank!