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

Abstract

Для розв’язання задачі Ins-Λ-CSP (реоптимізація Λ-CSP при додаванні одного обмеження) існує оптимальний наближений алгоритм з адитивною помилкою з константною складністю. При цьому відношення апроксимації алгоритму залежить від цілочислового розриву LP-релаксації вихідної задачі.

For solving Ins-Λ-CSP (reoptimization of Λ-CSP under insertion of one constraint) an optimal approximation algorithm with additive error exists. Approximation ratio of this algorithm depends on the integrality gap of LP relaxation of the initial problem.