Algorithmes d'approximation, partie I Avec quelle efficacité pouvez-vous emballer des objets dans un nombre minimum de boîtes ? Dans quelle mesure pouvez-vous regrouper des nœuds de manière à séparer à moindre coût un réseau en composants autour de quelques centres ? Ce sont des exemples de problèmes d'optimisation combinatoire NP-difficile. Il est très probablement impossible de résoudre de tels problèmes efficacement. Notre objectif est donc de donner une solution approximative qui peut être calculée en temps polynomial et qui, en même temps, a des garanties prouvables sur son coût par rapport à l'optimum.

Ce cours suppose la connaissance d'un cours standard d'algorithmique de premier cycle, et met particulièrement l'accent sur les algorithmes qui peuvent être conçus à l'aide de la programmation linéaire, une technique favorite et étonnamment réussie dans ce domaine. En suivant ce cours, vous serez exposé à un éventail de problèmes aux fondements de l'informatique théorique, et à de puissantes techniques de conception et d'analyse. A la fin du cours, vous serez capable de reconnaître, lorsque vous serez confronté à un nouveau problème d'optimisation combinatoire, s'il est proche d'un des quelques problèmes de base connus, et vous serez capable de concevoir des relaxations de programmation linéaire et d'utiliser l'arrondi aléatoire pour tenter de résoudre votre propre problème. Le contenu du cours, et en particulier les devoirs, est de nature théorique et ne comporte pas d'exercices de programmation. Ce cours est le premier d'un cours en deux parties sur les algorithmes d'approximation.