Градиентный алгоритм для систем независимости с отрицательными весами
Доказательство.
Так как
отлична от
матроида, то по лемме 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.
Для подготовки данной работы были использованы материалы с сайта omsu.omskreg/