Approximation Algorithms
Image credit: Robert Allison/SAS
This course took place at TU Berlin in the winter term 2020/2021. It is based on the book The Design of Approximation Algorithms, by D. Williamson and D. Shmoys (2010) and proposes a survey of techniques to analyze approximation algorithms for NP-hard problems, examplified by classical results of the literature.
Slides:
This slides are largely based on a former version prepared by Prof. Martin Skutella.
- Chapter 1: Introduction
- Chapter 2: Local Search and Greedy Algorithms
- Chapter 3: Rounding Data & Dynamic Programming
- Chapter 4: Deterministic Rounding of Linear Programs
- Chapter 5: Random Sampling & Randomized Rounding
- Chapter 6: The Primal-Dual Method
- Chapter 7: Hardness of Approximation & PCP theorem
Guillaume Sagnol
Senior Optimization Consultant
My research interests include convex & integer optimization, approximation algorithms, solving optimization problems with uncertain data and machine learning.