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