- 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.
Organization
- 8 lectures, each is 3 hours long.
- Lectures will be on Thursdays 12:45-15:45, starting on Dec. 11, and with two breaks somewhere in the middle of the semester.
- Lectures will be offered in English.
- Students may opt to give an oral presentation during the course, for a possible bonus of up to 2 points for the final grade.
- The final exam will be given in English and can be answered in either English or French.
Outline
- Dec. 11: Greedy Algorithm
- Dec. 18: Dynamic Program
- Jan. 8: Deterministic Rounding of Linear Programs
- to be continued
Bibliography
The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys.