Альфа-Аппроксимируемая задача: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) (Новая страница: «'''<math>\boldsymbol{\alpha}</math>-Аппроксимируемая задача'''([[alpha-Approximable problem|<math>\boldsymbol{\alpha}</math>-Approximable probl…») |
(нет различий)
|
Текущая версия от 14:16, 2 декабря 2011
[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.