Complexité Randomisée
Code APOGÉE : IFJCE170 | 6 ECTS | Validation : examen
Horaires hebdomadaires : 4h CM | Mutualisé avec : M2 MPRI
Édition 2024-2025 : Algorithmes d’approximation
Responsable du cours : Adrian Vladu (IRIF)
Enseignants : Chien-Chung Huang, David Saulpic
Objectifs
Le fil conducteur du cours est l’utilisation de l’aléatoire dans les algorithmes et la complexité. Cette année, le cours couvre les algorithmes d’approximation.
Organisation
- 8 cours magistraux, chacun de 3 heures
- Cours dispensés en anglais sur demande
- Devoirs réguliers
- Note finale : max(examen, (devoirs + 2×examen)/3)
Programme des cours
- Arrondi : Sac à dos, Bin packing, et ordonnancement
- Arrondi aléatoire de relaxations LP : set cover, optimisation sous-modulaire, satisfaisabilité maximale, multiway cut, maxcut dans les graphes denses
- Techniques primal-dual : conception de réseaux, multicut, localisation d’installations
- Arrondi itératif
- Plongement de métriques : Quadtree dans l’espace euclidien, plongement de Bartal ; lemme de Johnson-Lindenstrauss pour la réduction de dimension
- TSP : Algorithme de Christophides, schéma d’approximation d’Arora en ℝ²
- Programmation semi-définie : maxcut, jeux uniques et autres problèmes
- Sujets d’ouverture : Recherche locale, Sketching, Algorithmes en ligne…
Prérequis
- Algorithmes niveau M1
- Connaissances standard en probabilités discrètes
Stages/Internships
Des stages de recherche sont disponibles. Contactez les enseignants.
Bibliographie
- Vazirani, V. Approximation algorithms.
- Arora, S. Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and Other Geometric Problems.
- Fakcharoenphol, J., Rao, S. & Talwar, K. A tight bound on approximating arbitrary metrics by tree metrics.
- Dasgupta, S. & Gupta, A. An elementary proof of a theorem of Johnson and Lindenstrauss.
- Goemans, M. & Williamson, D. .879-approximation algorithms for MAX CUT and MAX 2SAT.