Direkt zum Inhalt

Lexikon der Mathematik: Approximationsproblem

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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos