Seminar Aktuelle Themen der Theoretischen Informatik
(Winter 2018/19)
Zeitplan
- Fr, 21.12.18: Spätest möglicher Termin für ein Treffen mit dem Betreuer
- Do, 07.02.19: Vorabeinreichung der vollständigen Folien für den Abschlussvortrag
- Do, 21.02.19 und Fr, 22.02.19: Vorträge
- So, 17.03.19: Abgabe der Ausarbeitung
Organisatorisches
- Dozent: Prof. Dr. Martin Hoefer
- Organisation: Daniel Schmand
- Für die erfolgreiche Teilnahme werden ein Vortrag und eine Ausarbeitung zu einem der Themen erarbeitet. Vortrag und Ausarbeitung können auf Deutsch oder Englisch verfasst werden.
- Die Vorträge werden als Blockseminar im Februar 2019 gehalten. Es wird erwartet, dass jeder Teilnehmer an allen Vorträgen teilnimmt.
- Der Vortrag soll eine Länge von 45 Minuten haben (plus Diskussion).
- Zur Vorbereitung vereinbaren Sie bitte
mindestens einmal einen Termin mit Ihrem Betreuer, um die Arbeit zu besprechen. - Die Ausarbeitung stellt das Thema der Arbeit, die Hauptresultate, sowie die Ideen der Analyse in eigenen Worten vor.
- Die Ausarbeitung sollte einen Umfang von 6-8 A4-Seiten (einzeilig, in 11pt Schriftgröße, 2-3cm Rand ringsum, Quellenverzeichnis und Abbildungen zählen nicht) haben.
Themen
- Alon, Fischer, Procaccia, Tennenholtz: Sum of Us: Strategyproof Selection from the Selectors
- Ascheuer, Krumke, Rambau: Online Dial-a-Ride Problems: Minimizing the Completion Time
- Bringmann: Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails
- Christodoulou, Mirrokni, Sidiropoulos: Convergence and Approximation in Potential Games
- Englert, Röglin, Spönemann, Vöcking: Economical Caching
- Englert, Röglin, Vöcking: Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP: Extended Abstract
- Goemans, Skutella: Cooperative Facility Location Games
- Jain, Vazirani: Equitable Cost Allocations via Primal–Dual-Type Algorithms
- Koch, Skutella: Nash Equilibria and the Price of Anarchy for Flows over Time
- Reiffenhäuser: An Optimal Truthful Mechanism for the Online Weighted Bipartite Matching Problem (bislang nicht veröffentlicht, Quelle wird per Mail verteilt)
- Rothvoß: A Simpler Proof for O(Congestion+Dilation) Packet Routing