Михайлюк В. А., Сергиенко И. В.
Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами

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.

PDF