ADM III Vorlesung: Online Optimierung, WS 2007/08

LV-Nr.: 0230 L 235

Aktuelles:

• Prüfungstermine können individuell vereinbart werden; kommt einfach vorbei (Raum 507) oder schreibt mir eine Email.

Ort und Zeit:

• Dienstags, 10:15 bis 11:45 Uhr, Raum MA 744.
• Donnerstags, 8:30 bis 10:00 Uhr, Raum MA 744.

Art der Veranstaltung:

• Es handelt sich um eine integrierte Veranstaltung: VL + Übungen (4 SWS).
• Die Vorlesung kann als ADM III angerechnet werden.

Inhalt:

In der Kombinatorischen Optimierung geht man zumeist davon aus, dass die Daten einer Probleminstanz a priori vollständig bekannt sind. Diese Annahme ist für viele Anwendungen nicht zutreffend. Betrachten wir als Beispiel das Problem der Aufzugsteuerung im Mathematikgebäude der TU Berlin. Idealerweise möchten wir einen Algorithmus entwickeln, der die durchschnittliche Wartezeit eines jeden Nutzers minimiert. Hierbei sind die Anfragen der Nutzer nicht von Anfang an bekannt, sondern erscheinen (willkürlich) über die Zeit verteilt. Können wir trotz dieses Informationsdefizits einen guten Algorithmus entwerfen? Dies ist eine typische Fragestellung, mit der man sich in der Online Optimierung beschäftigt.

In dieser Vorlesung beschäftigen wir uns mit Optimierungsproblemen unter verschiedenen Informationsmodellen. Die Online Optimierung wird hierbei ein zentrales Thema sein. Wir werden aber auch andere, nicht ganz so restriktive Informationsmodelle betrachten (zufällige/perturbierte Eingabeinstanzen, beschränkte Vorausschau, Resourcenerweiterung, etc.).

Ziel der Vorlesung ist es, einen Überblick über fundamentale Resultate dieses Bereiches zu geben und Techniken zur Charakterisierung der Qualität von Online Algorithmen zu vermitteln. Wir werden sowohl klassische Probleme der Online Optimierung betrachten als auch aktuelle Forschungsarbeiten.

Voraussetzungen:

Die Vorlesung richtet sich an Studierende der Mathematik/Informatik im Hauptstudium. Grundkenntnisse aus der Kombinatorischen Optimierung (ADM I + II) sind hilfreich, aber nicht zwingend erforderlich.

Scheinkriterien:

• Aktive Beteiligung an den Übungen.
• Gesamte Anzahl von Punkten für vorgerechnete Aufgaben beträgt mind. 3.
• Mündliche Rücksprache am Ende des Semesters.

Übungen:

• Die Übungen finden wöchentlich oder zumindest zweiwöchentlich statt, je nach Bedarf und Tempo.
• 1. Übungsblatt: [ub1.pdf]; Besprechung: 30.10.07.
• 2. Übungsblatt: [ub2.pdf]; Besprechung: 15.11.07.
• 3. Übungsblatt: [ub3.pdf]; Besprechung: 4.12.07; Lösung für Aufgabe 4: [ub3-lsg4.pdf].
• Weihnachtsübungsblatt: [ub4.pdf]; Besprechung: 8.1.08.
• 5. Übungsblatt: [ub5.pdf]; Besprechung: 29.01.07.

Literatur & Links:

1. Allan Borodin und Ran El-Yaniv, Online Computation and Competitive Analysis Cambridge University Press, 1998.
2. Handout: Geglättete Kompetitivitätsanalyse (smoothed competitive analysis); [pdf] (2.14 MB).
3. Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm, Becchetti et al., MOR 2006; [pdf]
4. Geglättete Kompetitivitätsanalyse für MTS: Topology Matters: Smoothed Competitiveness of Metrical Task Systems, Schäfer/Sivadasan, TCS, 2005; [pdf].
5. Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue, Buchbinder et al., ESA 2007; [pdf].
6. A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics, Fakcharoenphol/Rao/Talwar [pdf].
7. Online Dial-a-Ride Problems: Minimizing the Completion Time, Ascheuer, Krumke, Rambau, STACS 2000 [pdf].
8. Algorithms for the On-Line Travelling Salesman, Ausiello, Feuerstein, Leonardi, Stougie, Talamo, Algorithmica 29, 2001 [pdf].
9. On-line Scheduling to Minimize Average Completion Time Revisited, Megow, Schulz, ORL 32, 2004 [pdf].
10. List Scheduling in Order of alpha-Points on a Single Machine, Skutella, 2006 [pdf].

Kontakt:

• Dr. Guido Schäfer, MA 507, Tel. 030 314 21095, E-Mail: schaefer'at'math.tu-berlin.de, Sprechstunde nach Vereinbarung.
• Dr. Nicole Megow, MA 505, Tel. 030 314 25739, E-Mail: nmegow'at'math.tu-berlin.de, Sprechstunde nach Vereinbarung.
• Sekretariat, Gabriele Klink, MA 501, Tel. 030 314 25728, E-Mail: klink'at'math.tu-berlin.de, Sprechstunden: Mo., Di., Do. und Fr. 9:30 - 11:30.

Themen der Vorlesung:

• 1. Vorlesung, 16.10.: Einführung, Kompetitive Analyse, Request-Answer Games, Beispiele (Skifahrerproblem). Quelle: [1, Kap. 1, Kap. 7.1].
• 2. Vorlesung, 18.10.: Weitere Beispiele (Scheduling, Bin Packing, Lost Cow Problem).
• 3. Vorlesung, 23.10: Randomisierte online Algorithmen, blinder/adaptiver Gegenspieler, randomisierter Algorithmus für Skifahrerproblem. Quelle: [1, Kap. 4.1].
• 4. Vorlesung, 25.10.: Organisation von linearen Listen (List Accessing), Technik: Potentialfunktion, Analyse von Move-to-Front mittels Potentialfunktion. Quelle: [1, Kap. 1.2-1.4].
• Übung, 30.10.: Besprechung 1. Übungsblatt.
• 5. Vorlesung, 1.11.: List Accessing (Fortsetzung), Durchschnittstechnik (Averaging Technique), untere Schranke für List Acessing, Kompetitivität von TRANS. Einführung Paging Problem, Beweis der Optimalität für Longest-Forward-Distance. Quelle: [1, Kap. 1.5, Kap. 3].
• 6. Vorlesung, 6.11.: Paging (Fortsetzung), untere Schranke, deterministische online Algorithmen, Phasenpartition, Markierungsalgorithmen, LRU ist Markierungsalgorithmus. Quelle: [1, Kap. 3].
• 7. Vorlesung, 8.11.: Paging (Fortsetzung), k-Kompetitivität von Markierungsalgorithmen, randomisierter Algorithmus für Paging (Randmark), Technik: Yao's Prinzip, Exkurs: Zweipersonen Nullsummenspiel. Quelle: [1, Kap. 3, Kap. 4.3, Kap. 8].
• 8. Vorlesung, 13.11.: Fortsetzung (Exkurs Spieltheorie), Minimax Theorem, Loomies Lemma, Yao's Prinzip für online Probleme, untere Schranke für randomisierte Paging Algorithmen. Quelle: [1, Kap. 8].
• Übung, 15.11.: Besprechung 2. Übungsblatt.
• 9. Vorlesung, 20.11.: Einführung Metrische Tasksysteme, untere Schranke, Arbeitsfunktion. Quelle: [1, Kap. 9.1-9.3].
• 10. Vorlesung, 22.11.: Metrische Tasksysteme (Fortsetzung), Definition Arbeitsfunktion, online Arbeitsfunktionsalgorithmus (WFA), Kompetitivität von WFA. Quelle: [1, Kap. 9.4].
• 11. Vorlesung, 27.11.: Einführung geglättete Kompetitivitätsanalyse (smoothed competitive analysis), Anwendung auf Metrische Tasksysteme. Quellen: [2-4]
  • Definition Smoothed Competitive Analysis, Modell, Gegenspieler: Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm, Becchetti et al., MOR 2006; [pdf].
  • Handout der Vorlesung [pdf] (2.14 MB).
  • Geglättete Kompetitivitätsanalyse für MTS: Topology Matters: Smoothed Competitiveness of Metrical Task Systems, Schäfer/Sivadasan, TCS, 2005; [pdf].
  • Smoothed Analysis Homepage.
• 12. Vorlesung, 29.11.: Einführung Ad-Auctions, Exkurs: Lineare Programmierung und primal-duale Methode, primal-dualer online Algorithmus für Ad-Auction. Quellen: [5]
  • Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue, Buchbinder et al., ESA 2007; [pdf].
  • Computer Scientists Optimize Innovative Ad Auction, Robinson, SIAM News, Vol. 38 (3), 2005; [pdf].
• Übung, 4.12.: Besprechung 3. Übungsblatt.
• 13. Vorlesung, 6.12.: Fortsetzung Ad-Auctions. LP basierte obere Schranke für Profit einer optimalen Lösung, primal-dualer Algorithmus für Ad-Auction, Analyse der Kompetitivität. Quellen: s.o.
• 14. Vorlesung, 11.12.: Abschluss Beweis Ad-Auctions. Randomisierter primal-dualer online Algorithmus für das Skifahrerproblem. Quellen: s.o.
• 15. Vorlesung, 13.12.: k-Server Problem, Beweis untere Schranke. Quelle: [1, Kap. 10.1-10.3].
• 16. Vorlesung, 18.12.: k-Server Problem (Fortsetzung), Algorithmus Double Coverage für Linien, Beweis der Kompetitivität Quelle: [1, Kap. 10.4].
• 17. Vorlesung, 20.12.: k-Server Problem (Fortsetzung), Algorithmus Double Coverage für Bäume, Kompetitivität; Approximation von beliebigen Metriken durch Baummetriken. Quellen: [1, Kap. 10.4, 6].
  • A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics, Fakcharoenphol/Rao/Talwar [pdf].
• Übung, 8.1.: Besprechung Weihnachtsübungsblatt
• 18. Vorlesung, 10.1.: k-Server Problem (Fortsetzung), Algorithmus Balance für metrische Räume mit k+1 vielen Punkten, Beweis der k-Kompetitivität. Quelle: [1, Kap. 10.6]
• 19. Vorlesung, 15.1.: Timestamp Model (Online-Time Modell), Online Transportprobleme, Replan [7]
• 20. Vorlesung, 17.1.: Fortsetzung Kompetitive Analyse Replan [7], allgem. untere Schranke [8], SmartStart [7]
• 21. Vorlesung, 22.1.: Fortsetzung Analyse SmartStart, Minimierung max. bzw. durchschnittl. Flowtime: allgem. untere Schranke, Alternativen zur kompetitiven Analyse (reasonable load, fair and non-abusive adversary)
• 22. Vorlesung, 24.1.: Online Scheduling Probleme, Smith's Rule, Scheduling auf parallelen Maschinen mit Jobunterbrechung
• Übung & Vorlesung, 29.1.: WSPT Verallgemeinerung auf parallelen Maschinen [9]
• 23. Vorlesung, 31.1.: Online Scheduling ohne Jobunterbrechung, Listscheduling nach alpha-Punkten auf einer Maschine, deterministisch
• 24. Vorlesung, 5.2.: Forts. alpha-conversion technique - randomisiert; Flow-Time-Minimierung, Ressourcenerhöohung

Downloads:

Hier findet Ihr Material zur Vorlesung.

• List Scheduling in Order of alpha-Points on a Single Machine, Skutella, 2006 [pdf].
• On-line Scheduling to Minimize Average Completion Time Revisited, Megow, Schulz, ORL 32, 2004 [pdf].
• Online Dial-a-Ride Problems: Minimizing the Completion Time, Ascheuer, Krumke, Rambau, STACS 2000 [pdf].
• Algorithms for the On-Line Travelling Salesman, Ausiello, Feuerstein, Leonardi, Stougie, Talamo, Algorithmica 29, 2001 [pdf].
• A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics, Fakcharoenphol/Rao/Talwar [pdf].
• Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue, Buchbinder et al., ESA 2007; [pdf].
• Computer Scientists Optimize Innovative Ad Auction, Robinson, SIAM News, Vol. 38 (3), 2005; [pdf].
• Handout: Geglättete Kompetitivitätsanalyse (smoothed competitive analysis); [pdf] (2.14 MB).
• Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm, Becchetti et al., MOR 2006; [pdf]
• Geglättete Kompetitivitätsanalyse für MTS: Topology Matters: Smoothed Competitiveness of Metrical Task Systems, Schäfer/Sivadasan, TCS, 2005; [pdf].
• Einführung [pdf].
• Flyer zur Vorlesung [pdf].