If <$E k ~=~O ( log ~n )> and a predicate P is approximation resistant for the reoptimization of problem Max-EkCSP-P under insertion of a truth-value in the predicate and some constraint, then there exists a polynomial approximation algorithm with the ratio <$E q(P)~=~1 over {2~-~d(P)}>, where <$Ed(P)~=~2 sup -k | P sup -1 (1) |> is a threshold "random" approximation ratio of P. The approximation ratio q(P) is threshold.

Індекс рубрикатора НБУВ: В127.4

Рубрики:

Теорія обчислюваності. Складність обчислень

Шифр НБУВ: Ж29144 Пошук видання у каталогах НБУВ 
Повний текст  Наукова періодика України 

---

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"