|
-
Ключові слова:
математика, mathematics, mathematique, matematyka, matematica, mathematica ; оптимізація, оптимизация, optimization
-
Анотація:
Показано, що якщо для проблеми Max - E2CSP - P iснує полiномiальний оптимальний (пороговий) 1/2-наближений алгоритм, то для проблеми Ins - Max - E2CSP - P (реоптимiзацiя Max - E2CSP - P з додаванням одного обмеження) iснує полiномiальний оптимальний (пороговий) '(?)-наближений алгоритм, де '(?) = 12?? . Цей результат застосовується для проблем з P = XOR (реоптимiзацiя Max Cut) i з P = OR (ре оптимізація Max 2-Sat) при виконаннi унiкальної iгрової гiпотези (UGC).
-
Є складовою частиною документа:
-
Теми документа
-
Окремі фонди та колекції КНУ // праці авторів КНУТШ, труды авторов КНУТШ, работы авторов КНУТШ
|
