Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами

Abstract

Якщо k=O(logn) і предикат P спадково апроксимаційно-стійкий для реоптимізації проблеми Max-EkCSP-P, при вставці нового істинісного значення в предикат і деякого обмеження існує поліноміальний наближений алгоритм з відношенням апроксимації, яке є пороговим.If k=O(logn) 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 algorithm with the approximation ratio that is threshold