CS-627 / 2 crédits

Enseignant: Svensson Ola Nils Anders

Langue: Anglais


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)
  • Type: optionnel

Semaine de référence

Cours connexes

Résultats de graphsearch.epfl.ch.