max planck institut
mpii logo Minerva of the Max Planck Society

Teaching: Beyond Worst-Case Analysis (Winter 2013/2014)

Beyond Worst-Case Analysis, Winter 2013/14

Martin Hoefer and Marvin Künnemann

The traditional worst-case analysis conducted in the analysis of algorithms often leads to predictions and evaluations that differ significantly from performance observed in practice. In particular, algorithms that are designed to optimize worst-case performance are not necessarily successful in solving practical instances. The seminar treats several recent approaches using randomized adversarial scenarios that overcome the limited view of worst-case analysis. The topics of the seminar include smoothed analysis, secretary problems, and more general approaches to stochastic online optimization.

Time: Thursday, 10:00 am (s.t.) to 12 am
First meeting: First Thursday of the winter 2013/14 term, i.e., 17th of October.
Room: 024 on the ground floor of the MPI building (E1.4)
Prerequisites: You should bring a solid background in algorithms and data structures. This is an advanced seminar. The papers are challenging and a proper preparation of your talk will require some effort. The target audience of this reading group are master students and advanced bachelor students.
Content: In each session we have at most two paper presentations (each 45 minutes + discussion). Students aiming to get credits give a regular talk and write a short summary about the paper.
Credits: You earn the usual 7 credit points for a seminar if you (i) give a regular presentation of the paper given to you, and (ii) write a short summary (about 5 pages).
News for students:
  • If you want credit for the course, please register with Marvin by sending him a short mail ([first name] before October 24. Please also specify a paper that you want to present. (Feel free to register even if you did not attend the introductory lecture.)
Date Speakers Topic
Oct 17 Martin Introduction to the seminar
Jan 16 Manoj,
Stochastic Analyses for Online Combinatorial Optimization Problems
An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions
Jan 23 Nicolas,
Smoothed Analysis of the k-means method
Smoothed Analysis of the Successive Shortest Path Algorithm
References for talks:
Available papers:
Smoothed Analysis
Secretary Problems
Stochastic Online Optimization and Prior-Independent Mechanism Design

More Courses of the Algorithms and Complexity Group

Search MPII (type ? for help)