12 au 14 juin 2006
Centre de recherches mathématiques
Organisateurs: Joseph Cheriyan (Waterloo)
et Michel Goemans (MIT)
La plupart des problèmes d’optimisation combinatoire sont NP-difficiles, c’est-à-dire qu’ils ne peuvent être résolus en temps polynomial que si les classes P et NP sont identiques. Depuis trois décennies, les chercheurs essaient donc de concevoir des algorithmes d’approximation qui fournissent, en temps polynomial, des solutions «quasi-optimales» dont l’écart à l’optimum peut être borné supérieurement. Depuis quinze ans, ces chercheurs ont décrit de nouvelles techniques, basées sur l’arrondissement des valeurs de programmes linéaires, la programmation semi-définie et le plongement des espaces métriques. Ils ont aussi montré, en utilisant par exemple le théorème PCP, qu’il était difficile de trouver des solutions approchées de certains problèmes. En particulier, Khot, Kindler, Mossel et O’Donnell [2005] ont prouvé récemment qu’il n’était pas possible d’améliorer la borne de l’algorithme de Goemans et Williamson [1995] pour le problème de la coupe maximale (en supposant que P et NP ne sont pas identiques et que la conjecture des jeux uniques est vraie). Les conférenciers invités à cet atelier feront le point sur les résultats récents, c’est-à-dire les algorithmes eux-mêmes et les «résultats négatifs».