Анотація. Якщо 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-теорема, аппроксимационно-устойчивые предикаты.