Seminar: Beyond Worst-Case Analysis
General Information
Course instructors: Andreas S. Schulz, Alexander Grosz
The presentations will take place in seminar room 2906.DG.009 (local room number 6009).
The standard approaches for estimating the running time of algorithms are often insufficient to explain their practically observed behaviour: the pessimistic worst-case analysis may rely on specific structures in artificial instances which do not appear in practice, while the optimistic average case analysis often assumes overly simplified probabilistic models of the input.
In this seminar, we discuss several modern approaches of bridging this observational gap in the theoretical analysis:
- Parameterized analysis and fixed-parameter tractable algorithms
- "Islands of tractability" and deterministic structured data-models
- Perturbation and approximation stability
- Semi-random data models as a way of augmenting average-case analysis
- Smoothed analysis of algorithms
Schedule
| Kick-Off Meeting | tbd |
| Preference submission | tbd |
| Presentation draft submission | 14 days before your presentation date |
| Presentations | tbd |
Topics
tbd
Literature
- Tim Roughgarden, Beyond the Worst-Case Analysis of Algorithms, 2021
- Selected publications