La notion de recherche locale est liée à la notion de voisinage : un optimum local est une solution qui n'en connaît pas de meilleure parmi ses voisines. Par exemple, un ensemble stable de sommets est un optimum 1-local (une seule modification est autorisée d'une solution à une solution voisine) si l'ajout d'un sommet violerait la stabilité de l'ensemble. Dans ce cadre, la finalité de notre approche est la suivante : plutôt que de concevoir un "bon" algorithme pour résoudre un problème donné, on étudie le comportement des problèmes vis-à-vis d'un type d'algorithme donné. Précisément, nous posons la question : quels sont les problèmes dont tous les optima locaux sont des bonnes solutions, au sens de l'approximation au pire des cas ?

Les résultats sont fortement dépendants de la structure de voisinage étudiée : h-bornée (d'une solution à une solution voisine, on change au plus h composantes) ou h-bornée miroir (d'une solution à une solution voisine, on change au plus h ou au moins n-h composantes). Ils dépendent aussi de la fonction d'évaluation (qui n'est pas nécessairement l'objectif initial) qui désigne les optima locaux (ex. : pour Max k-Sat, on obtient de meilleurs résultats, sur le problème initial, en considérant les optima locaux d'une version pondérée particulière).