Об исследовании устойчивости задач на матроидах
3
все выглядит сложнее. Входными параметрами задачи будем считать
матрицу
A
весов ребер графа
,
G V E
c
n
вершинами и
m
реб-
рами и множество
S
D
всех остовных деревьев этого графа. Кроме
того, заданы число
B
и вторые веса на ребрах. Для ребра
e
вес
c e
—
плата за увеличение длины ребра на единицу. Ребра могут
возмущаться только в сторону увеличения.
Другими словами, в пространстве
m
R
векторов
А
задана метрика
1
l
и ребра могут возмущаться только в сторону увеличения. (В то
время как в [1, 6] рассматриваются произвольные независимые воз-
мущения элементов.) Среди всех возмущенных задач, в которых
суммарная плата за увеличение длин ребер не превосходит
В
, требу-
ется найти такую, длина оптимальной траектории которой макси-
мальна. Это называется
задачей максимизации оптимума с фиксиро-
ванным бюджетом
. В работе [9] предлагается алгоритм сложности
3 2
2
2
log
O n m n m
. Алгоритм состоит из
O nm
итераций, на каж-
дой из которых не более
m
раз используется процедура Cheng
—
Cunningham [11] для нахождения «прочности» (strenght) графа.
Вышеописанный подход на основе радиуса устойчивости можно
непосредственно применить к данной задаче в случае, если все
1
c e
.
Для этого достаточно уметь вычислять радиус устойчивости.
После нахождения радиуса устойчивости получаем новую мат-
рицу весов
.
A
При этом нам известно, все или не все траектории
имеют в ней одинаковую длину. Если длина всех траекторий одина-
кова, то процесс заканчивается. Из теоремы 1 [1, с. 142, 143] следует,
что сложность нахождения радиуса устойчивости в рассматриваемом
случае
3
2
2
log
O n m n m
.
В противном случае сравниваем радиус устойчивости с числом
B
.
Если он меньше
В
, то берем возмущенную задачу Pr
A
и ищем ее ра-
диус устойчивости. Продолжаем так до тех пор, пока не получим за-
дачу с бесконечным радиусом устойчивости (в ней веса всех ребер
одинаковы) либо пока сумма всех этих радиусов не станет равной
(или превзойдет)
В
.
Легко показать, что результат не зависит от выбираемых возму-
щающих векторов.
Так как всего не более
m
различных значений весов ребер, то общая
трудоемкость алгоритма та же, что и в [9], т. е.
3 2
2
2
log
O n m n m
.
Если же допустить произвольные возмущения весов ребер, то ре-
зультаты [9] никак не характеризуют устойчивость задачи, как это
следует из теоремы 1 в работе [1, с. 142, 143].
