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