Il s'agit de proposer, pour les problèmes dits difficiles d'optimisation combinatoire (problèmes NP-difficles), des algorithmes approchés (on ne prétend pas résoudre les problèmes à l'optimum) mais efficaces, en imposant une complexité polynomiale des algorithmes (efficacité en temps) et en estimant la qualité des solutions produites au pire des cas (les bornes proposées pour évaluer les solutions sont valables pour toute solution retournée par l'algorithme, sur toute instance du problème).
On dit par exemple, dans le cadre du rapport classique (mesure usuelle d'évaluation des algorithmes), qu'un algorithme est une 2/3-approximation pour un problème de maximisation si l'on est en mesure d'assurer que toute solution qu'il produit est de valeur au moins "2/3 x la valeur optimale".

Les résultats proposés sont essentiellement de deux ordres : énoncer qu'un problème est approximable à un niveau donné par le biais d'un algorithme dédié problème (démonstration explicite), énoncer qu'un problème est (ou n'est pas) approximable à un niveau donné par le biais de réduction, c'est-à-dire en exprimant le problème étudié comme un cas particulier (ou cas général) d'un problème connu (démonstration implicite).