Статья: Градиентный алгоритм для систем независимости с отрицательными весами
Fr(F) - это множество элементов, каждый из которых может быть добавлен к F без нарушения его независимости. Именно из этих элементов градиентный алгоритм выберет на очередном шаге самый "тяжелый" для добавления к F.
Введем новую характеристику системы независимости:
Она характеризует "узкое место" в работе градиентного алгоритма.
Будем называть предбазами максимальные по включению независимые множества, не являющиеся базами. Тогда определение (4) можно записать как
поскольку каждое независимое подмножество, которое не является базой, содержится в некоторой предбазе и .
Теорема 2. 1) Для систем независимости , базы которых представляют собой все r-элементные подмножества (r-однородные матроиды),
где n=|E|, r=ur(E).
2) Для систем независимости, отличных от r-однородных матроидов,
Доказательство. 1) Очевидно, т.к. |Fr(F)|=n-|F|=n+1-ur(E) для любой предбазы F.
2) Если матроид (не r-однородный), то . Пусть F - база A. Т.к. |F|<|A|, то F не является базой матроида и .
Если не матроид, то по лемме 1 . Заметим, что .
Замечание. На различных системах независимости может принимать значения от 1 до n=|E| включительно, причем только в случае 1-однородного матроида.
Теорема 3 (оценка кривизны). Для любой системы независимости, отличной от 1-однородного матроида, имеет место оценка
Доказательство. Если система независимости представляет собой r-однороный матроид, , то k=1 и оценка (6) верна. Иначе , следовательно, и т.к. и (), то
Пусть дана система независимости , через (через ) обозначим такое минимальное число, что существует весовая функция , ровно () значений которой отрицательны, и SA (S0) содержит по крайней мере один элемент с отрицательным весом.
Теорема 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 непосредственно следует