Search academic texts

Information × Registration Number 0514U000185, Doctoral dissertation Status д.ф.-м.н. Date 28-02-2014 popup.evolution o Title Estimates of complexity of postoptimality analysis and approximation algorithms for the reoptimization of discrete programming problems Author Mikhailyuk Victor Oleksiiovych, popup.head Sergienko Ivan Vasylyovych popup.opponent Глибовець Микола Миколайович popup.opponent Козін Ігор Вікторович popup.opponent Семенов Володимир Вікторович Description Встановлено, що проведення постоптимального аналізу (в найгіршому випадку) NP-складних задач само по собі є NP-складним. Для встановлення верхніх оцінок відношення апроксимації наближених алгоритмів реоптимізації використовувалися напіввизначена (SDP-) та лінійна (LP-) релаксації вхідних задач. Отримано достатні умови існування поліноміальних оптимальних наближених або порогових (верхня оцінка відношення апроксимації співпадає з нижньою) алгоритмів реоптимізації узагальнених задач про виконуваність Ins-Max-EkCSP-P (CSPs): апроксимаційна стійкість предиката P; істинність унікальної ігрової гіпотези (UGC), а також точна оцінка цілочислового розриву SDP- або LP-релаксації задачі. На основі аналізу реоптимізаційних алгоритмів задачі про покриття множинами (при заміні 0 на 1 або 1 на 0 в матриці обмежень) підтверджена можливість якісних "стрибків" з одного класу апроксимації в інший з кращою якістю наближення. Це "стрибки" з класу Log-APX в клас APX. Показано, що для реоптимізації задачі про покриття множинами при додаванні елемента в довільну множину або видалення з неї не існує поліноміально наближеної схеми (PTAS). Запропонований підхід до проектування поліноміальних оптимальних наближених (порогових) алгоритмів реоптимізації для задач дискретного програмування має місце та у випадку сублінійних алгоритмів, зокрема константної складності. На основі отриманих результатів теоретичних досліджень розроблено практичний алгоритм постоптимального аналізу для пошуку методом гілок і меж точних розв'язків сім'ї споріднених задач про рюкзак. Обчислювальний експеримент встановив його ефективність. Registration Date 2014-02-28 popup.nrat_date 2020-04-04 Close