Э.Н. Гордеев
4
Если рассматриваются только возмущения в сторону увеличения,
то для нахождения радиуса устойчивости необходима модификация
алгоритма из [10], которая, по сути, сводится к извлечению из него
процедуры нахождения минимального протыкающего множества,
т. е. процедуры Cheng – Cunningham.
Мы привели здесь только один пример из множества постановок,
касающихся исследования устойчивости решений в задачах дискрет-
ной оптимизации, в рамках которого многие результаты либо уже
получены явно, либо сравнительно легко получаются на основе тео-
рии устойчивости, разработанной в [1–7].
ЛИТЕРАТУРА
[1] Гордеев Э.Н. Исследование устойчивости в оптимизационных задачах на
матроидах в метрике
l
1
.
Кибернетика и системный анализ
, 2001, № 2,
с. 132–144.
[2] Sotskov Yu.N., Leontev V.K., Gordeev E.N. Some concepts of stability analy-
sis in combinatorial optimization.
Discrete Applied Mathematics
, 1995, no. 58,
рр. 169–190.
[3] Гордеев Э.Н., Леонтьев В.К. Общий подход к исследованию устойчиво-
сти решений в задачах дискретной оптимизации.
Журнал вычислитель-
ной математики и математической физики
, 1996, № 36, c. 66–72.
[4] Леонтьев В.К. Устойчивость в линейных дискретных задачах. Яблон-
ский С.В., ред.
Проблемы кибернетики
. Москва, Наука, 1979, вып. 35,
с. 169–185.
[5] Леонтьев В.К., Гордеев Э.Н. Качественное исследование траекторных за-
дач.
Кибернетика.
Киев, 1986, № 5, с. 82–90.
[6] Гордеев Э.Н. Алгоритмы полиномиальной сложности для вычисления
радиуса устойчивости в двух классах траекторных задач.
Журнал вычис-
лительной математики и математической физики
, 1987, т. 27, № 7,
с. 984–992.
[7] Гордеев Э.Н. Устойчивость решений в задаче о кратчайшем пути на гра-
фе.
Дискретная математика
, 1989, т. 1, № 3, с. 39–46.
[8] Tarjan R.E. Sensitivity analysis of minimum spanning trees and shortest paths
trees.
Inf. Proc. Letters
, 1982, vol. 14, no. 1, рр. 30, 31.
[9] Fredericson G.N., Solis-Oba R. Increasing the weight of minimum spanning
trees
. Proc. 7th Annual ACM-SIAM Symp. on Discrete Algotithms
. Amster-
dam, 1996, рр. 539–546.
[10] Fredericson G.N., Solis-Oba R. Efficient Algorithms for Robustness in
Matroid Optimization.
Proc. 8th Annual ACM-SIAM Symp. on Discrete Al-
gotithms
. Amsterdam, 1997, рр. 659–668.
[11] Cheng E., Cunningham W.H. A faster algorithm for computing the strength of
a network.
Inf. Proc. Letters,
1994, vol. 49, рр. 209–212.
Статья поступила в редакцию 28.06.2013
Ссылку на эту статью просим оформлять следующим образом:
Гордеев Э.Н. Об исследовании устойчивости задач на матроидах.
Инженер-
ный журнал: наука и инновации,
2013, вып. 11. URL:
/
it/hidden/1002.html
