Градиентный алгоритм для систем независимости с отрицательными весами (стр. 2 из 2)

Теорема 4.

для любой системы независимости .

Доказательство. Пусть

. Присвоим элементам множества F0 вес |E|, элементам Fr(F0) вес -1, а остальным элементам вес 0. Тогда SA и S0 будут содержать элементы с отрицательным весом и, следовательно, и (всего отрицательных весов ).

Если число "отрицательных" элементов меньше

, то SA и S0 не могут содержать элементов с отрицательным весом (для SA это очевидно. Если же S0 содержит "отрицательные", то рассмотрим подмножество его "неотрицательных" элементов C. В силу определения мы можем добавлять к C "неотрицательные" элементы, пока не получим базу, вес которой строго больше веса S0). Следовательно, и .

Замечание. Отрицательность здесь не играет принципиальной роли. Основной ее смысл в том, что выделяется класс "отрицательных" элементов, вес каждого из которых меньше веса любого "неотрицательного". К примеру, теорему 4 можно интерпретировать так: S0 и SA не содержат ни одного из

наименьших по весу элементов.

3. Оценки погрешности градиентного алгоритма

Лемма 2. Пусть

- произвольная система независимости, - весовая функция, допускающая отрицательные веса. Если при этом веса всех элементов SA неотрицательны, то справедлива оценка (2).

Доказательство. Рассмотрим новую задачу, в которой все отрицательные веса исходной задачи сделаем нулевыми, оставив тот же порядок элементов (для новой задачи используются обозначения c', S'A, S'0). Тогда S'A=SA, c'(S'A)=c(SA) и

. А поскольку в новой задаче все веса неотрицательны, то теорема 1 справедлива и

Из теоремы 4 и леммы 2 непосредственно следует

Теорема 5. Пусть дана система независимости

и весовая функция , количество отрицательных значений которой меньше, чем . Тогда

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

Хорошо известна теорема Радо-Эдмондса, которая утверждает, что если система независимости является матроидом, то для произвольной неотрицательной весовой функции градиентный алгоритм всегда находит точное решение задачи (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.