Cybernetics And Systems Analysis
International Theoretical Science
Journal
Mikhailyuk V.A.,1 Sergienko I.V.2
1V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine,
e-mail: mikhailyukvictor2@gmail.com
2V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine,
e-mail: aik@public.icyb.kiev.ua.
Abstract. If k=O(log n) and a predicate Р 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 q(P)=1/(2-d(P)), where d(P)=2-k|P-1(1)| is a threshold «random» approximation ratio of Р. The approximation ratio q(P) is threshold. Refs: 23 titles.
Keywords: reoptimization, C-approximation algorithm, discrete Fourier analysis, PCP theorem, approximation resistant predicate.
