- title:
- Approximation Algorithms
Algorithmes d'approximation - manager:
- Hang Zhou
- ects:
- 3
- period:
- 2
- hours:
- 24
- weeks:
- 8
- hours-per-week:
- 3
- lang:
- themes:
- Algorithms, Discrete Math/Graphs
- year:
- 2025
- [approx]
- Approximation Algorithms
Algorithmes d'approximation
- Language:
- Period:
- 2.
- Duration:
- 24h (3h/week).
- ECTS:
- 3.
- Themes: Algorithms, Discrete Math/Graphs
- Manager:
- Hang Zhou.
Instructor
Hang Zhou (École Polytechnique)
Overview
Given an NP-hard optimization problem, how well can it be approximated in polynomial time? In this course, we study techniques in the desgin of approximation algorithms for fundamental optimization problems.
Outline
The course consists of 8 lectures of 3 hours each. Lectures are given in English.
- Greedy Algorithms and Local Search
- Rounding Data and Dynamic Programming
- Deterministic Rounding of Linear Programs
- Random Sampling and Randomized Rounding of Linear Programs
- Randomized Rounding of Semidefinite Programs
- The Primal-Dual Method
- Cuts and Metrics
- Traveling Salesman Problem and Capacitated Vehicle Routing
Bibliography
The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys.