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 rapprochées à 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».