Skip to content
Technical University of Munich

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). This room is not in Garching. Some helpful advice for your presentation can be found here.


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

Oct 23, 17:00 via Zoom Kick-Off Meeting
Oct 30 Send topic preferences (X > Y > Z) to Alexander Grosz via email
14 days before your presentation date Presentation draft submission
tbd Presentations

Topics

  • A: M. Etscheid and H. Röglin, “Smoothed Analysis of Local Search for the Maximum-Cut Problem,” 2017, DOI.
  • B: B. Manthey and R. Veenstra, “Smoothed Analysis of the 2-Opt Heuristic for the TSP,” 2013. DOI.
  • C: M.-F. Balcan, A. Blum, and A. Gupta, “Clustering under approximation stability,” 2013, DOI.
  • D: F. N. Abu-Khzam, M. R. Fellows, M. A. Langston, and W. H. Suters, “Crown Structures for Vertex Cover Kernelization,” 2007, DOI.
  • E: N. Alon, R. Yuster, and U. Zwick, “Color-coding,” 1995, DOI.
  • F: D. Lokshtanov, D. Marx, and S. Saurabh, “Slightly superexponential parameterized problems,” 2011, DOI
  • G: A. Blum and J. Spencer, “Coloring Random and Semi-Random k-Colorable Graphs,” 1995, DOI.
  • H: S. Agrawal, Z. Wang, and Y. Ye, “A Dynamic Near-Optimal Algorithm for Online Linear Programming,” 2014, DOI.

You may suggest another topic/paper, but it should be approved by us ahead of the preference submission deadline. We encourage a look into the book referenced below.

Literature

  • Tim Roughgarden, Beyond the Worst-Case Analysis of Algorithms, 2021
  • Selected publications (see list of topics above)
To top