Hier so wie ich das noch im Kopf habe:

Prfung findet in seinem Bro statt. Man sitzt zu dritt (Assi ist Protokollant) an einem Runden Tisch und wird vom Vcking befragt. Man hat Papier und Stift zur Verfgung als Erklrhilfe.

Dauer: 30 Minuten

Ich wurde 1.0 geprft: 

=====================
V: Ja dann fangen wir am besten gleich mal an. Wir hatten bei Makespan Scheduling verschiedene Heuristiken. Was war das so?

I: [gesagt dass es welche fr identische und allgemeine gibt. Dann fr identische Maschinen LL und LPT beschrieben was die machen]

V: Mhm, ok. Wie gut sind die so? Wir hatten fr LL ja ne Schranke als 2-Approximation

I: Ja da geht sogar (2-1/m) und LPT ist eine 4/3 Approximation.

V: Wie kann man das fr LL zeigen?

I: [Beweis erklrt mit letztem zugeteilten Job wegnehmen etc. Dann zweimal opt als untere Schranke. Gesagt, dass man ein m-tel des letzten Jobs noch in die Summe mit reinnehmen kann]

V: Und LPT? Der hatte ja 4/3. Wie haben wir das denn gemacht?

I: [Gesagt, dass wir angenommen haben er htte einen schlechteren Approximationsfaktor und dann gezeigt haben dass daraus folgen wrde das der Algo optimal ist, was er aber nicht ist. Mehr wusste ich nmlich nicht wirklich ^^]

V: Ok, und wie haben wir das gezeigt?

I: [*Schwitz* ^^] Aehh... Wir haben... aeh

V: [Hilft]

I: Aeh keine Ahnung

V: Doch doch das wissen Sie schon. Wir haben da was ber den letzten Job gesagt, dass der grer als 1/3 opt sein muss, und dass ... [erklaert alles]

I: Hm ja stimmt.

V: Ist 4/3 denn das beste was geht?

I: Nein, wir knnen beliebig gut werden, denn wir haben gezeigt, dass es ein Polynomial Time Approximation Scheme [ich liebe dieses Wort] gibt. Nur dass hier die Laufzeit extrem steigt.

V: Ok, wie funktioniert das?

I: Wir teilen unsere Jobs zunchst in groe und kleine Jobs ein, ach nee wir brauchen erst noch den optimalen Makespan Z, den uns ein Orakel verrt. Also das Orakel werden wir dann mit einfacher Binrsuche implementieren. Die Grenze fr groe und kleine Jobs ist dann epsilon mal Z [Vcking unterbricht]

V: Ja genau die kleinen streuen wir dann am Ende noch so zwischen die groen.

I: Ja, die groen skalieren wir erstmal runter und zwar um den Faktor epsilon quadrat mal Z. Wir kennen nun also auch hierfr den Makespan, da wir den genauso runterskalieren. Dann runden wir alles. Hierbei entsteht ein Fehler der [Vcking unterbricht]

V: Ja der ist ja recht klein.

I: Genau. Der Rundungsfehler ist epsilon. Jetzt knnen wir, da wir den optimalen Makespan kennen und die Anzahl der Maschinen, effizient ein Bin-Packing durchfhren. Und dann die Zuteilung bernehmen.

V: Mhm ok, Wie machen wir das mit dem Bin-Packing?

I: Jaa... [*grins*]. Also das haben wir mit dynamischer Programmierung gemacht. Die rekursive Funktion die wir uns dafr definiert haben, nimmt als Argumente die Anzahlen der einzelnen Objekte die wir packen wollen. Dann nehmen wir um von i nach i+1 zu kommen bestimmte Elemente weg die wir in eine Kiste packen.

V: Also was sagt uns die Funktion denn berhaupt?

I: Ja das ist die Anzahl der Bins die wir brauchen

V: Ja warten Sie ich schreib ihnen das mal auf, das geht vielleicht besser: [Schreibt: "f(n_1,n_2,...) = "] [berlsst mir den Rest]

I: [Schreibe: " = 1 + min_{q\in Q} f(n_1 - q_1, ..."] Wobei die q_i

V: Ja klar die q_i sind aus q. Ja richtig. Und das geht in welcher Zeit zu berechnen?

I: Aehm. Polynomiell auf jeden Fall.

V: Ja wie lsen wir das denn jetzt?

I: Durch Backtracking.

V: Hm. Ne das ist so nicht korrekt

I: Ja wir machen uns ne Tabelle.

V: Aha

I: Ja also quadratische Zeit?

V: Ne, die Tabel..

I: Achso ja die ist hochdimensional. k-dimensional deswegen ist das nmlich auch so langsam.

V: Richtig.

I: Ja mit Backtracking meinte ich, dass er sich beim Durchgehen durch die Tabelle merkt, welche Sachen er in welche Bins gepackt hat.

V: Achso ok, das hatte ich anders verstanden. Naja, und dann skalieren wir die Jobs wieder hoch und so, ok. Und bei allgemeinen Maschinen?

I: Da haben wir das ganze versucht als ILP zu formulieren zu relaxieren und anschlieend zu runden. Wir haben fr die "Straightforward" Idee aber bemerkt, dass wir ein zu groes Integrality Gap haben und das an dem Beispiel gezeigt, dass nur ein Job mit Gre 1 auf m Maschinen verteilt wird. Da sieht man dann, dass der Makespan in echt 1 ist, aber durch das ILP Runden wir auf 1/m kommen, also ein sehr groer Unterschied besteht. Daraufhin haben wir uns einen zweiten Ansatz angeschaut, bei dem der Makespan durch ein Orakel bestimmt wird, und wir nicht mehr nach dem Makespan optimieren sondern den mit in die Nebenbedingungen einbauen. Das Entscheidende war, dass wir nur die (i,j) Zuweisungen betrachten, die den Makespan nicht berschreiten.

V: Ja genau. Und wenn wir dann unser LP gelst haben?

I: Dann weisen wir zunchst die eindeutigen Jobs mit x_ij = 1 zu und tragen die restlichen in einen Graphen ein, wobei zwischen Maschine und Job genau dann eine Kante ist wenn x_ij > 0 [erklaert, dass wir dann einen Allokationsgraphen machen etc. Habe erklrt dass wir immer Maschinenknoten als Bltter haben und die zuordnen und dass am Ende hchstens ein Kreis bleibt und wie wir den zuordnen]

V: Und warum hat der Graph immer diese Struktur, also hchstens |V| Kanten?

P: Hmm.. [gute frage]. 

V: Wie war das mit gewissen Nebenbedingungen des LPs?

P: Ach ja da waren welche immer genau erfllt. Also die Nichtnegativittsbedingungen. Also nee, die insbesondere. Aeh..

V: [Malt Simplextableau auf, Schreibt oben N links M dran] Wieviele Variablen sind jetzt in unserer Basis?

I: N-M. Ach ne quatsch das sind die Nichtbasisvariablen. M also.

[Haben dann zusammen einen Weg zur Antwort gefunden, dass es hchstens |V| Kanten geben kann, weil alle anderen Variablen 0 sind]

V: Ok, und wie haben wir gezeigt dass es eine 2-Approximation ist?

P: Aehmm. puh! Ne ich wei nicht ich bin mir da zu unsicher.

V: Ach geben Sie doch nicht immer so schnell auf. Was ist mit den sicher zugeteilten Jobs?

I: Ja die verursachen hchstens Makespan von opt.

V: Ja, wegen der ILP Bedingung. Und die anderen, die wir durch den Graphen zuordnen?

I: Puh. [denk]. Hm ne wei ich nicht

V: [Hilft noch bisschen und erklrt dann, dass ja nochmal maximal ein Job pro Maschine zugeordnet wird]

I: Achso ja und das ist dann nochmal hchstens opt also 2 opt.

V: Ja. Da sind wir jetzt schonmal bei Linearen Programmen, machen wir doch gleich da weiter. Was ist das?

I: [Erklrt dass wir Nebenbedingungen haben, die den Raum in Halbrume spalten und eine Maximierungsrichtung. Erzhlt, dass es Simplex, Ellipsoid und Innere-Punkte-Methode gibt]

V: Ja dann erklren Sie doch mal wie die Ellipsoidmethode das lst.

I: [Hatte ihn erst falsch verstanden und mit Simplex angefangen er hat mich dann unterbrochen.]

V: [Malt geometrisches LP auf und groe Ellipse drumrum mit Mittelpunkt]

I: Ja also wir suchen uns dann eine Nebenbedingung raus, die unseren Punkt ausschliet. Dann verschieben wir die parallel so dass sie durch unseren Punkt verluft. Dann haben wir die Ellipse in zwei Teile geteilt. [Habe alles anhand der Zeichnung erklrt].

V: Ok, jetzt wissen wir, dass wir es immer weiter einschrnken, und wann hrt das ganze auf?

I: Wir kennen eine minimale Gre der Ellipse, bei der wir wissen, dass wenn sie erreicht ist, der Mittelpunkt im Polyhedron liegen muss, wenn das LP lsbar ist.

V: Richtig. In welcher Grenordnung bewegen wir uns da?

I: Hm das war irgendwas mit... also die Basis hab ich vergessen, aber wir haben im Exponenten O(L^2) bzw -O(L^4) fr die kleine Kugel.

V: Ok, wir haben also eine obere Schranke und eine untere. Wie kommen wir jetzt zur polynomiellen Anzahl der Schritte?

V: Also wenn wir jetzt wissen wir haben einen Faktor um den das Volumen der Ellipse schrumpft. Und polynomielle Schranken...

I: Das hrt sich an als wr das schon die Antwort ^^

V: Naja fast. [Schreibt Bruch auf]

I: Hm ne ich weiss es nicht.

V: Ach, das ist gerade wahrscheinlich einfach zu simpel ;) Wir nehmen natrlich einfach den Logarithmus und dann haben wirs...

I: Ah ok. Ja das macht Sinn. Den Zweier-Logarithmus.

V: So dann machen wir mal einen Sprung zu Min-Cost Flow. Was haben wir da fr Anstze gehabt?

I: Also wir haben einen Fluss mit Wert |W| und optimieren die Kosten bis sie optimal sind. Wenn es im Restnetzwerk einen Kreis mit negativen Kosten gibt, dann knnen wir den maximal mglichen Fluss ber diesen Kreis zu unserem aktuellen addieren. Da der Kreis die Flusserhaltung auf allen Knoten einhlt, ndert sich der Wert unseres Flusses nicht, aber die Kosten sinken. Und da diese Existenzbedingung eine Genau-Dann-Wenn Bedingung ist, knnen wir die auch als Terminierungsbedingung fr den Algorithmus benutzen, da wir wissen, dass wenn es keinen solchen Kreis mehr gibt, wir optimal sind.

V: Ok, wir hatten da aber eine schnelle Variante

I: Ja das war das Min-Mean-Cycle-Cancelling. Hier nehmen wir immer den Kreis mit den geringsten durchschnittlichen Kosten. Also das heit, die Summe aller Kantenkosten auf dem Kreis geteilt durch die Anzahl der Kanten.

V: Und woher wissen wir das unser Algorithmus terminiert. Bzw. dass wir immer einen solchen Kreis finden, wenn der Fluss nicht kostenoptimal ist?

I: Ja also wir wissen auf jeden Fall, dass es eine Zirkulation als Differenz zwischen dem optimalen und unserem Fluss gibt. Da der Wert der Flsse gleich ist, hat diese Zirkulation nmlich den Wert 0. Jetzt knnen wir mit Tiefen- oder Breitensuche Kreise in der Zirkulation finden. Wenn wir jetzt einen gefundenen Kreis betrachten, gibt es irgendwo auf diesem Kreis eine Flaschenhalskante. Wenn wir den Fluss also entlang dieses Kreises maximal erhhen, wird die gesttigt und fllt somit weg. Wenn wir in der Zirkulation als M Kanten haben, knnen wir das ganz hchstens M mal machen

V: Ja korrekt. Wie finden wir den Min-Mean-Cycle. Oder woher kennen wir den Wert?

I: Das machen wir wieder mit dynamischer Programmierung. Dazu definieren wir uns Knotenpotentiale d_k(v), die fr jeden Knoten v die Kosten des kostenkrzesten Pfades mit Lnge k angeben, der bei v endet.
Der Wert des Min-Mean-Cycles ist dann [schreibe die Formel fr alpha auf]

V: Ja ok, ich glaub Ihnen, dass Sie den Rest knnen ;) Ok dann warten Sie bitte drauen.