Жадные алгоритмы аппроксимации: различия между версиями

'''Отказ от субмодулярности'''

 

Отказ от субмодулярности – непростой вопрос, уже долгое время остающийся открытым. Однако это возможно благодаря наблюдению Дю и коллег относительно утверждения (2) в [1]: субмодулярность –f применяется для приращения вершины <math>y_j \;</math>, принадлежащей к оптимальному решению <math>C^* \;</math>.

 

 

В силу гибкости упорядочения вершин <math>y_j \;</math> можно организовать его таким образом, чтобы контролировать величину <math>\Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1} )</math>. Это позволит успешно справиться с задачей MCDS.