Algorithmic Toolbox
Frequency
Only this year
Summary
This course covers numerous powerful algorithmic techniques (greedy, local search, linear programming, multiplicative weight update, ...). The concepts are studied in clean and simple settings so as to emphasize the main algorithmic ideas over problem specific details.
Content
The goal of this course is to give starting PhD students a toolbox of algorithmic techniques. The course emphasises the illustration of the main ideas of these techniques and we will apply them in the simple and clean setting of the set cover problem. The algorithmic techniques that we plan to cover include:
- Greedy algorithms
- Local search algorithms
- Linear programming
- Randomized rounding (independent, threshold, exponential clocks)
- Duality (primal-dual algorithms, dual fitting, and the use of complementarity slackness)
- Multiplicative weight update
- Online algorithms in adversarial and random order streams (primal-dual, potential function, and projection based).
In addition, to attending the lectures, students are required to submit a project report where they apply one of the algorithmic techniques in a more complex setting.
Keywords
Algorithms, set cover
Learning Prerequisites
Required courses
Undergraduate algorithms and basic discrete math/probabilities
Assessment methods
Project report
Resources
Notes/Handbook
Learning Outcomes: To apply a rich algorithmic toolbox in order to solve their favorite problems.
Websites
Dans les plans d'études
- Forme de l'examen: Rapport de TP (session libre)
- Matière examinée: Algorithmic Toolbox
- Cours: 20 Heure(s)