Seminar Network Design
Wintersemester 07/08
Prof. Dr. Friedrich Eisenbrand
Zielgruppe:
Das Seminar richtet sich an Studierende der Mathematik im Hauptstudium und an Studierende im Masterstudiengang Informatik (Module III.2.1 Algorithmen 1 und III.2.2 Algorithmen 2).
Termine:
Das Seminar beginnt am 14. Januar und findet dann zweimal pro Woche jeweils
Mo 16:00-18:00
Di 14:30-16:30
statt.
Inhalt:
Viele Optimierungsprobleme, welche in Theorie und Praxis auftreten, stellen sich bei genauerer Betrachtung als Netzwerk-Design Problem heraus. Grob gesprochen deckt dieser Begriff Optimierungsprobleme ab, denen implizit oder explizit ein Graph zugrunde liegt. In diesem Seminar wollen wir einige interessante Probleme herausgreifen und algorithmische Lösungen für diese besprechen.
Ziele:
Die Ziele dieser Veranstaltung sind zweigeteilt. Zum einen sollen alle Teilnehmer das Gebiet des Network Design kennen lernen und einige Probleme, Methoden und Tricks am Ende des Seminars beherrschen. Sie sollen hier jedoch auch und vielleicht vor allem lernen, wie ein Thema selbständig erarbeitet und wiedergegeben wird. Die Wiedergabe besteht aus einer schriftlichen Ausarbeitung und einer Präsentation (Vortrag) über das behandelte Thema. Die Ausarbeitung im Umfang von 8-17 Seiten erfolgt mit eigenen Worten, d.h. eine rein wörtliche Übersetzung ist nicht ausreichend. Die Anfertigung der Ausarbeitung erfolgt vor der Präsentation und soll sicherstellen, dass die Inhalte verstanden wurden.
Es finden sich viele Anleitungen zum guten Seminarvortrag im Netz. Vor allem sollte man sich auf die Inhalte konzentrieren und keine Gimmicks, Animationen etc. verwenden, es sei denn, es ist didaktisch sinnvoll.
Kriterien zur Scheinvergabe:
Die Benotung wird durch die Qualität der Präsentation und der Ausarbeitung bestimmt.
Zusatzregeln für Informatiker:
In Anschluss an das Seminar findet eine mündliche Prüfung über 4 Seminarthemen statt. Die zu prüfenden Themen können aus den präsentierten Themen frei ausgewählt werden. Diese Prüfung muss zum Leistungsnachweis bestanden werden.
Themen:
Die folgenden Vortragsthemen werden präsentiert:
- Hu´s Theorem, Jaroslaw Klose 14. Januar [9], Ausarbeitung, Folien
- Integer Dekomposition, Martin Niemeier, 15. Januar [9], Ausarbeitung, Folien
- Routing auf dem Hypercube, Natalya Moriz, 21. Januar [2], Ausarbeitung, Folien
- K-Median, Grischa Ende, 22. Januar [1], Ausarbeitung, Folien
- Facility Location, Peter Kling, 28. Januar [1], Ausarbeitung, Folien
- Steiner Tree, Natalie Richert, 4. Februar [5], Ausarbeitung, Folien
- VPND, Lars Schaefers, Ausarbeitung, Folien
- Jonas Schrieb, k-Cut & Multiway Cut, Ausarbeitung, Folien
- Malte Röhs, Feedback Vertex Set, Ausarbeitung, Folien
Literatur:
[1] Vijay Vazirani, Approximation Algorithms, Springer
[2] Mitzenmacher & Upfal, Probability and Computing, Cambridge University Press
[3] Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems. Journal of the ACM Vol. 45, 1998
[4] Sariel Har Peled, Approximation Algorithms in Geometry, Lecture Notes
[5] Zelikovsky, An 11/6-approximation algorithm for the network steiner problem, Springer
[6] Eisenbrand, Grandoni, An improved approximation algorithm for virtual private network design, SODA'05
[7] Gupta, Kumar, Roughgarden, Simpler and better approximation algorithms for network design, STOC'03
[8] Eisenbrand, Grandoni, Oriolo, Skutella, New approaches for virtual private network design, ICALP'05
[9] A. Schrijver, Combinatorial Optimization Vol I-III, Springer Verlag