Résumé :
En optimisation combinatoire classique, de nombreux algorithmes ont été proposés afin d'optimiser de nombreux critères d'optimisation et ce pour des applications très variées. Des techniques algorithmiques diverses ont été développées et ont permis la résolution optimale ou quasi-optimale des problèmes d'optimisation fondamentaux. L'une des approches les plus fondamentales se fonde sur la programmation linéaire.
Dans la première partie de cours, nous étudierons un cas plus spécifique de cette approche, celui de la méthode primal-dual, qui est utilisée pour résoudre en temps polynomial des problèmes combinatoires fondamentaux, soit optimalement (flot maximum), soit avec une bonne approximation (Couverture, Arbres de Steiner). Nous présenterons les principes de cette méthode et quelques-unes de ces applications à des problèmes classiques (Couverture) ou plus récents (Arbres de Steiner).
Si en optimisation combinatoire classique l'objectif est l'optimisation d'un critère unique, dans le cas de l'optimisation multi-critère une solution est évaluée en fonction de plusieurs critères d'optimalité. Les problèmes d'optimisation multi-critère ont été largement étudiés dans le passé, et ce particulièrement dans des domaines tels que la recherche opérationelle, la micro-économie et plus récemment en informatique. Les résultats existant peuvent être regroupés en trois catégories. Dans la première on optimise un seul critère mais une contrainte est imposée sur le second. Dans la seconde, on cherche des résultats concernant la qualité de l'approximation qui peut être obtenue simultanément pour les divers critères d'optimalité. Enfin, dans la troisième on cherche à déterminer le compromis (courbe de Pareto) existant entre l'optimisation des divers critères.
Dans la seconde partie du cours, nous discuterons de ces trois questions et présenterons quelques applications dans le cas des problèmes bi-critère.
Références :
La première partie de ce cours reprend essentiellement le livre de V.V. Vazirani (Approximation Algorithms, Springer, 2001) et un article récent de K. Jain et V.V. Vazirani (Application of Approximation Algorithms to Cooperative Games, STOC'01, pp. 364-372).
La seconde partie est basée
sur la thèse de H. Hoogeveen (CWI 92), sur un article de C. Stein
et J. Wein (On the Existence of Schedules that are Near-Optimal for both
Makespan and Total Weighted Completion Time, Operations Research Letters,
21, 1997), sur un article récent de C.H. Papadimitriou et M. Yannakakis
(On the Approximability of Trade-Offs and Optimal Access of Web Sources,
FOCS 2000, pp. 86-92) et sur un article de E. Angel, E. Bampis et A. Kononov
(A FPTAS for Approximating the Unrelated Parallel Machine Scheduling Problem
with Costs, Proc. of ESA'01, pp. 194-205).