ein Problem der Annäherung eines zu bestimmenden exakten Wertes durch eine angenäherte (approximative) Lösung.

Ein Approximationsproblem kann somit als Optimierungsproblem aufgefaßt werden, bei dem nicht eine optimale Lösung berechnet werden muß, sondern nur eine Lösung, deren Güte (Güte eines Algorithmus) eine vorgegebene Grenze einhält.

Approximationsprobleme sind die innerhalb der Approximationstheorie und, in etwas anderer Sichtweise, der Optimierung, in fundamentaler Weise untersuchten Probleme.

Ein NP-schweres Problem kann als Approximationsproblem bei jeder Güte 1 + ϵ, ϵ > 0, in polynomieller Zeit lösbar sein, so z. B. das Rucksackproblem. Aus praktischer Sicht sind oftmals effizient berechnete Lösungen für das Approximationsproblem mit kleiner vorgegebener Güte wesentlich besser als mit großem Aufwand berechnete Lösungen des zugrundeliegenden Optimierungsproblems.