Реєстраційний номер
0514U000185, Докторська дисертація
На здобуття
д.ф.-м.н.
Дата захисту
28-02-2014
Статус
Захищена
Назва роботи
Оцінки складності постоптимального аналізу та наближені алгоритми реоптимізації для задач дискретного програмування
Здобувач
Михайлюк Віктор Олексійович,
Керівник Сергієнко Іван Васильович
Опонент Глибовець Микола Миколайович
Опонент Козін Ігор Вікторович
Опонент Семенов Володимир Вікторович
Установа, організація, у вченій раді якої відбудеться/відбувся захист
Інститут кібернетики ім.В.М.Глушкова НАН України
Опис
Встановлено, що проведення постоптимального аналізу (в найгіршому випадку) NP-складних задач само по собі є NP-складним. Для встановлення верхніх оцінок відношення апроксимації наближених алгоритмів реоптимізації використовувалися напіввизначена (SDP-) та лінійна (LP-) релаксації вхідних задач. Отримано достатні умови існування поліноміальних оптимальних наближених або порогових (верхня оцінка відношення апроксимації співпадає з нижньою) алгоритмів реоптимізації узагальнених задач про виконуваність Ins-Max-EkCSP-P (CSPs): апроксимаційна стійкість предиката P; істинність унікальної ігрової гіпотези (UGC), а також точна оцінка цілочислового розриву SDP- або LP-релаксації задачі. На основі аналізу реоптимізаційних алгоритмів задачі про покриття множинами (при заміні 0 на 1 або 1 на 0 в матриці обмежень) підтверджена можливість якісних "стрибків" з одного класу апроксимації в інший з кращою якістю наближення. Це "стрибки" з класу Log-APX в клас APX. Показано, що для реоптимізації задачі про покриття множинами при додаванні елемента в довільну множину або видалення з неї не існує поліноміально наближеної схеми (PTAS). Запропонований підхід до проектування поліноміальних оптимальних наближених (порогових) алгоритмів реоптимізації для задач дискретного програмування має місце та у випадку сублінійних алгоритмів, зокрема константної складності. На основі отриманих результатів теоретичних досліджень розроблено практичний алгоритм постоптимального аналізу для пошуку методом гілок і меж точних розв'язків сім'ї споріднених задач про рюкзак. Обчислювальний експеримент встановив його ефективність.
Дата реєстрації
2014-03-26
Додано/оновлено в НРАТ
2020-04-04 / 2026-06-29
