Course info

Prerequisites

• Mathematical maturity.
• Basic knowledge of discrete algorithms and optimization and probability theory.

Aim of the course

Understanding and applying methods to analyze algorithms for which the classical worst-case analysis fails to explain the performance.

Traditionally, the classical analysis of algorithms focuses on the worst-case behavior. E.g., what is the worst case running time, or the worst case approximation or competitive ratio. In many settings, this gives too pessimistic insights and does not reflect empirical observations. A classic example is the Simplex Algorithm for Linear Programming, which takes exponential time is worst case, but works spectacularly fast in practice.
In recent years, there has been increasing focus on exploring more realistic models for various problems and developing a robust theory for the design and analysis of algorithms. This has led to both beautiful mathematical ideas and new algorithmic insights. A nice example is the smoothed analysis framework developed by Spielman and Teng to explain the empirical behavior of Simplex.
This course will focus on methods and techniques to rigorously analyze algorithms beyond the classical worst-case analysis, with special focus on heuristics that work well in practice. We will consider a wide variety of  algorithmic problems spanning different areas such as classic NP-Hard problems, online algorithms, compressed sensing and machine learning. These problems will be explored both using probabilistic approaches such as  average-case analysis, smoothed analysis and semi-random input models and deterministic approaches such as local-search, resource augmentation, stability and perturbation resilience, refined analysis based on input parameters such as conditions numbers or non-degeneracy conditions.

Lecture Notes / Literature

Lecturers

Nikhil Bansal (TUE) and Bodo Manthey (UT)