Михайлюк В. О. Оцінки складності постоптимального аналізу та наближені алгоритми реоптимізації для задач дискретного програмування

Встановлено, що проведення постоптимального аналізу (в найгіршому випадку) NP-складних задач само по собі є NP-складним. Для встановлення верхніх оцінок відношення апроксимації наближених алгоритмів реоптимізації використовувалися напіввизначена (SDP-) та лінійна (LP-) релаксації вхідних задач. Отримано достатні умови існування поліноміальних оптимальних наближених або порогових (верхня оцінка відношення апроксимації співпадає з нижньою) алгоритмів реоптимізації узагальнених задач про виконуваність Ins-Max-EkCSP-P (CSPs): апроксимаційна стійкість предиката P; істинність унікальної ігрової гіпотези (UGC), а також точна оцінка цілочислового розриву SDP- або LP-релаксації задачі. На основі аналізу реоптимізаційних алгоритмів задачі про покриття множинами (при заміні 0 на 1 або 1 на 0 в матриці обмежень) підтверджена можливість якісних "стрибків" з одного класу апроксимації в інший з кращою якістю наближення. Це "стрибки" з класу Log-APX в клас APX. Показано, що для реоптимізації задачі про покриття множинами при додаванні елемента в довільну множину або видалення з неї не існує поліноміально наближеної схеми (PTAS). Запропонований підхід до проектування поліноміальних оптимальних наближених (порогових) алгоритмів реоптимізації для задач дискретного програмування має місце та у випадку сублінійних алгоритмів, зокрема константної складності. На основі отриманих результатів теоретичних досліджень розроблено практичний алгоритм постоптимального аналізу для пошуку методом гілок і меж точних розв'язків сім'ї споріднених задач про рюкзак. Обчислювальний експеримент встановив його ефективність.