CS-627 / 2 crédits

Enseignant: Svensson Ola Nils Anders

Langue: Anglais


Only this year


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.


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.


Algorithms, set cover

Learning Prerequisites

Required courses

Undergraduate algorithms and basic discrete math/probabilities

Assessment methods

Project report



Learning Outcomes: To apply a rich algorithmic toolbox in order to solve their favorite problems.


Dans les plans d'études

  • Forme de l'examen: Rapport de TP (session libre)
  • Matière examinée: Algorithmic Toolbox
  • Cours: 20 Heure(s)
  • Type: optionnel

Semaine de référence

Cours connexes

Résultats de graphsearch.epfl.ch.