Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність

Abstract

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

Для решения задачи Ins−Λ−CSP (реоптимизация ограниченной Λ−CSP задачи при добавлении произвольного ограничения) существует оптимальный приближенный алгоритм с аддитивной ошибкой с константной сложностью. Отношение аппроксимации алгоритма зависит от целочисленного разрыва линейной релаксации исходной задачи.

To solve the problem Ins−Λ−CSP (reoptimization of a bounded-degree Λ−CSP problem under the insertion of an arbitrary constraint), there is an optimal constant-time approximation algorithm with additive error. The approximation ratio of the algorithm depends on the integral gap of a linear relaxation of the initial problem.