Optima locaux à garantie de performance

Considérant les voisinages h-bornés et h-bornés miroir, nous posons la question suivante : pour quels problèmes tous les optima locaux sont-ils de bonne solutions au sens de l'approximation au pire des cas, où l'optimalité locale peut être définie soit relativement à l'objectif initial du problème, soit relativement à un objectif altéré ? Différents résultats, positifs comme négatifs, ont été établis ; nous en donnons ici quelques-uns à titre d'illustration. Nous montrons par exemple que les optima 3-locaux de MaxK3-free Partial Subgraph assurent une 3/(B+1)-approximation dans les graphes à degré borné par B [MPT04] ; dans ce cadre, les solutions voisines d'une solution s donnée sont toutes les solutions réalisables que l'on peut obtenir à partir de s en moins de trois modifications. Concernant le problème du voyageur de commerce, le fameux voisinage 2-opt produit des optima locaux qui sont une 1/2-approximation différentielle [MPT02] ; les optima 2-locaux des problèmes de partitionnement héréditaires (Bin packing, Coloration etc..) en font de même.
Pour Max 2CCSP, on établit que le rapport des optima locaux pour un voisinage "miroir" 2-borné est de 1/3 [MPT031] ; cette fois, une affectation T' est voisine de T si toutes les variables coïncident, ou toutes sont opposées, sauf peut-être une. Pour MaxkSat, le rapport est de 2k/(2k+1) pour les optima locaux du même voisinage, mais évalués par l'objectif NAESat [MPT031] : T est meilleure que T' si le nombre de clauses contenant conjointement des littéraux vrais et faux est plus important dans T que dans T'. Pour ces deux derniers résultats, on montre que l'agrandissement de la taille du voisinage (passer du 1-borné au 2-, 3- etc. -borné) ne permet pas d'améliorer la performance des optima locaux.
En revanche, MaxSubsetSum par exemple ne garantit pas la qualité de ses optima locaux [MPT031].