- 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.
- 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.
Lecture Dates
- Dec. 11
- Jan. 8
- Jan. 15
- Jan. 22
- Jan. 29
- Feb. 5
- Feb. 19
- Feb. 26
- Final exam: Mar. 12
Bibliography
The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys.