Статья: Градиентный алгоритм для систем независимости с отрицательными весами

Теперь рассмотрим ситуацию, когда нет ограничения на число элементов отрицательного веса.

Хорошо известна теорема Радо-Эдмондса, которая утверждает, что если система независимости является матроидом, то для произвольной неотрицательной весовой функции градиентный алгоритм всегда находит точное решение задачи (1). Нетрудно показать, что этот результат остается верным и для случая, когда допускаются отрицательные веса.

Однако из следующей теоремы вытекает, что если система независимости отлична от матроида, то в общем случае невозможно получить оценку погрешности градиентного алгоритма.

Теорема 6. Если система независимости отлична от матроида, то для произвольных существует такая весовая функция , что и . Причем, если , то существует с этим же свойством.

Доказательство. Так как отлична от матроида, то по лемме 1 , |B|=lr(E), и . Рассмотрим два случая:

1) . Среди всех баз, которые являются подмножествами выберем максимальную по мощности базу C. Присвоим всем элементам вес, условно говоря, , элементам вес , а элементу u вес . Если S0 содержит u, то , иначе, очевидно, . А т.к. , то нетрудно понять, что .

2) . Среди всех баз, которые являются подмножествами , выберем базу C, для которой минимальна. Пусть v произвольный элемент . Присвоим элементам вес , элементу u вес , элементу v вес , а всем остальным элементам вес 0 (в этом случае ). Т.к. минимальна, то любая база, веса отличного от и не содержащая u, содержит v, поэтому .

В обоих случаях можно так упорядочить элементы равного веса, что SA=A и .

Замечание. Задачу максимизации с весами можно интерпретировать как задачу минимизации с весами (весовой функцией c'(e)=-c(e)). Теорема 6 показывает, что для любой системы независимости, отличной от матроида, и задачи минимизации на ней (все веса неотрицательные) в принципе не может существовать гарантированной оценки погрешности градиентного алгоритма.

Список литературы

Hausmann D., Korte B. Lower bounds on the worst-case complexity of some oracle algorithms // Discrete Math. 1978. V.24. N 3. P.261-276.

Korte B. Approximative algorithms for discrete optimization problems // Annals of Discrete Math. Amsterdam: North-Holland. 1979. V.4. P.85-120.