Оцiнки Шора для зваженого числа стiйкостi графа

Анотація

Описано застосування техніки двоїстих лагранжевих квадратичних оцінок Н. З. Шора до дослідження задачі про максимальну зважену незалежну множину вершин графа. Наведено отримані за її допомогою дві верхні оцінки Н. З. Шора для $\alpha(G,w)$ – максимального зваженого числа стійкості графа, які можна знайти за поліноміальний час. Перша оцінка $\psi(G,w)$ пов’язана з квадратичною моделлю задачі про максимальну зважену незалежну множину вершин графа та співпадає з відомим числом Ловаса $\vartheta(G,w)$. Друга оцінка $\psi_1(G,w)$ відповідає цій же квадратичній моделі, яка доповнена сімейством функціонально надлишкових квадратичних обмежень, та спроможна покращити точність верхньої оцінки $\alpha(G,w)$ у спеціальних сімействах графів. Показано, що $\psi(G,w)= \alpha(G,w)$, якщо граф є дводольним або досконалим, а $\psi_1(G,w)= \alpha(G,w)$, якщо граф є $t$- або $W_p$-досконалим. На основі цих виділених класів графів продемонстровано технологію формування нових класів графів, для яких зберігається поліноміальна розв’язність задачі знаходження максимального зваженого числа стійкості графа. Таким чином, на прикладі задачі про максимальну зважену незалежну множину вершин графа показано, яким чином техніка лагранжевих оцінок може бути застосована до вирішення проблеми виділення класів поліноміально розв’язних задач комбінаторної оптимізації. Дана концепція може бути використана як для уточнення існуючих оцінок цільової функції в задачах комбінаторної оптимізації, так і для обґрунтування їх поліноміальної розв’язності.