SMF

Exposé Bourbaki 1045 : Difficulté d'approximation d'après Khot, Kindler, Mossel, O'Donnell,...

Exposé Bourbaki 1045 : Hardness of approximation after Khot, Kindler, Mossel, O'Donnell,...

Pierre PANSU
Exposé Bourbaki 1045 : Difficulté d'approximation d'après Khot, Kindler, Mossel, O'Donnell,...
  • Consulter un extrait
  • Année : 2013
  • Tome : 352
  • Format : Électronique
  • Langue de l'ouvrage :
    Français
  • Class. Math. : 05C12, 05C85, 46N10, 68Q17, 68R10, 68W25, 90C22, 91B14
  • Pages : 83-120

Du point de vue de la complexité algorithmique, de nombreux problèmes d'optimisation combinatoire (comme 3SAT, MAX CUT, SPARSET CUT) sont équivalents À première vue : ils sont NP-complets. Dans certains cas, même des versions approchées, où on se contente d'une solution qui réalise une fraction donnée de l'optimum, restent NP-complètes. C'est l'essence du théorème PCP (1992). Depuis peu, pour MAX CUT, on conjecture la valeur exacte du seuil d'approximabilité. Cela fait intervenir de la géométrie et de l'analyse harmonique discrète.

From the point of view of computational complexity, several combinatorial optimization problems (e.g. MAX 3SAT, MAX CUT, SPARSEST CUT) are equivalent, at first sight: all are NP-complete. In certain cases, even approximate versions, where solutions are merely required to achieve a given fraction of the optimum, remain NP-complete. This is the meaning of the PCP Theorem (1992). For MAX CUT, one is now able to conjecture the exact value of the approximation threshold, thanks to progress relying on geometry and discrete harmonic analysis.

Algorithme d'approximation, difficulté d'approximation, plongement métrique, programmation semi-définie, choix social
Approximation algorithm, hardness of approximation, metric embedding, semidefinite programming, social choice
Prix
Adhérent 7 €
Non-Adhérent 10 €
Quantité
- +