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

• Опубліковано в: : Доповіді НАН України
• Дата: 2013
• Автор: Михайлюк, В.О.
• Формат: Стаття
• Мова: Українська
• Опубліковано: Видавничий дім "Академперіодика" НАН України 2013
• Теми: Інформатика та кібернетика
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/85635
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність / В.О. Михайлюк // Доповiдi Нацiональної академiї наук України. — 2013. — № 4. — С. 38–42. — Бібліогр.: 7 назв. — укр.

Для розв’язання задач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.