Seminar Approximationsalgorithmen (Sommer 2023)
Aktuelles
| Nr. | Zeit | Titel |
|---|---|---|
| 1 |
Montag, 9:00 - 12:30 |
On PAC Learning Using Winnow, Perceptron, and a Perceptron-like Algorithm |
| 2 | Algorithmic Information Design in Multi-Player Games: Possibility and Limits in Singleton Congestion | |
| 3 | A Threshold of ln n for Approximating Set Cover | |
| 4 |
Montag, 14:00 - 15:10 |
A Linear Time Approximation Algorithm for Weighted Matchings in Graphs |
| 5 |
Dienstag, 9:00 - 12:30 |
Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings |
| 6 | Approximation Schemes for Scheduling on Parallel Machines | |
| 7 | Graph Balancing: a Special Case of Scheduling Unrelated Parallel Machines |
Vorläufiger Zeitplan
14.04.2023, 14:00 Uhr: Vorbesprechung21.04.2023: Einreichung Themenwünsche13.05.2023: Spätest möglicher Termin für eine erste Besprechung17.06.2023: Abgabe der Ausarbeitung - erste Version01.07.2023: Abgabe der Ausarbeitung - finale Version15.07.2023: Vorabeinreichung der vollständigen Folien für den Abschlussvortrag31.07.-01.08.2023: Vorträge
Themen
- A Linear Time Approximation Algorithm for Weighted Matchings in Graphs (BSc)
Doratha E. Drake Vinkemeier, and Stefan Houghardy - Tight Approximation Bounds for the Seminar Assignment Problem (BSc, English only)
Amotz Bar-Noy, and George Rabanca - Packet Routing: Complexity and Algorithms (BSc)
Britta Peis, Martin Skutella, and Andreas Wiese - On PAC Learning Using Winnow, Perceptron, and a Perceptron-like Algorithm (BSc)
Rocco A. Servedio - Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination. (BSc, English only)
Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos - Tractable Fragments of the Maximum Nash Welfare Problem (BSc)
Jugal Garg, Edin Husic, Aniket Murhekar, and Laszlo A. Vegh - Approximation Schemes for Scheduling on Parallel Machines (MSc)
Noga Alon, Yossi Azar, Gerhard J. Woeginger, and Tal Yadid - An Approximation Algorithm for Fully Planar Edge-Disjoint Paths (MSc)
Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Kevin Schewior, and Jens Vygen - Graph Balancing: a Special Case of Scheduling Unrelated Parallel Machines (MSc, English only)
Tomas Ebenlendr, Marek Krcal, and Jiri Sgall - A Threshold of ln n for Approximating Set Cover (MSc)
Uriel Feige - Stochastic Submodular Cover with Limited Adaptivity (MSc)
Aprit Agarwal, Sepehr Assadi, and Sanjeev Khanna - Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings (MSc, English only)
Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni
Organisatorisches
- Dozent: Prof. Dr. Martin Hoefer
- Organisation: Tim Koglin, Marco Schmalhofer, Giovanna Varricchio
- 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 (voraussichtl. 31. Juli und 01. August 2023) veranstaltet. 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, spätestens bis 13. Mai, 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 10 A4-Seiten (einzeilig, in 11pt Schriftgröße, 2-3cm Rand ringsum, Quellenverzeichnis und Abbildungen zählen nicht) haben.
- Hier finden Sie Hinweise für eine erfolgreiche Seminarteilnahme.