UGC + Majority is stablest => borne optimale d’inapproximabilité pour MAX-CUT
- Groupe de lecture de complexité algorithmique
Optimalité de l’algorithme de Goemans-Williamson pour MAXCUT conditionnellement à UGC, d’après Khot, Kindler, Mossel et O’Donnell
- Cet évènement est passé