М 691 Михайлюк, В. О. Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності [Текст] / В. О. Михайлюк // Доповіді Національної академії наук України. - 2013. - № 1. - С. 37-41. - Бібліогр. в кінці ст.
Кл.слова (ненормовані): Оптимум глобальний -- Задача Max-Cut -- Гіпотеза ігрова -- Результат Рагхавендри -- Математичне сподівання -- Алгоритм наближений Анотація: При виконанні унікальної ігрової гіпотези для розв'язання задачі Ins-Max-EkCSP-P (реоптимізація при додаванні довільного обмеження) при k=const існує поліноміальний оптимальний наближений алгоритм. |