Альфа-Апроксимируемая задача

[math]\displaystyle{ \boldsymbol{\alpha} }[/math]-Аппроксимируемая задача([math]\displaystyle{ \boldsymbol{\alpha} }[/math]-Approximable problem) — задача [math]\displaystyle{ A }[/math] максимизации (минимизации), для которой существует полиномиальный алгоритм [math]\displaystyle{ {\mathcal A} }[/math] такой, что для всех входов [math]\displaystyle{ I }[/math] он порождает решение [math]\displaystyle{ {\mathcal A}(A) }[/math], чьё значение по крайней мере (самое большое) в [math]\displaystyle{ \boldsymbol{\alpha} }[/math] раз превосходит оптимальное.

Литература

• Workshop. Cadenabbia, 1996 // Lect. Notes Comp. Sci., 1997, vol. 1197.