Аннотация. Если k=O(log n) и предикат P наследственно аппроксимационно-устойчивый для реоптимизации проблемы Max-EkCSP-P, при вставке нового истинностного значения в предикат и некоторого ограничения существует полиномиальный приближенный алгоритм с отношением аппроксимации q(P)=1/(2-d(P)), где d(P)=2^-k|P^-1(1)| — пороговое «случайное» отношение аппроксимации предиката P. Отношение аппроксимации q(P) является пороговым. Библиогр.: 23 назв.

Ключевые слова: реоптимизация, C-приближенный алгоритм, дискретной Фурье-анализ, Теорема PCP, аппроксимационный-устойчивый предикат.