Инженерный журнал: наука и инновацииЭЛЕКТРОННОЕ НАУЧНО-ТЕХНИЧЕСКОЕ ИЗДАНИЕ
свидетельство о регистрации СМИ Эл № ФС77-53688 от 17 апреля 2013 г. ISSN 2308-6033. DOI 10.18698/2308-6033
  • Русский
  • Английский
Статья

Об исследовании устойчивости задач на матроидах

Опубликовано: 18.11.2013

Авторы: Гордеев Э.Н.

Опубликовано в выпуске: #11(23)/2013

DOI: 10.18698/2308-6033-2013-11-1002

Раздел: Информационные технологии

За последние двадцать лет появились десятки статей, посвященных исследованию устойчивости в задачах оптимизации, при этом многие результаты, опубликованные в отечественных научных журналах в 1970-1980-е годы, игнорируются, а более поздние публикации цитируются как базовые и оригинальные. Цель данной статьи - обратить на это внимание на одном примере - исследование устойчивости в задачах на матроидах. Для случая нормы Чебышева в пространстве возмущений параметров задачи проблема устойчивости всесторонне изучена в работах 1980-х годов, на которые авторы публикаций 1990-х и более поздних годов вообще не ссылаются. Для случая метрики l1 задача является технически более сложной, поэтому нельзя говорить о полной эквивалентности опубликованных ранее результатов и появившихся позднее. Однако эти результаты тесно между собой связаны, что и показано в данной статье. При этом область теории матроидов взята просто в качестве примера. Аналогичные ситуации возникают и для других задач.


Литература
[1] Гордеев Э.Н. Исследование устойчивости в оптимизационных задачах на матроидах в метрике l1. Кибернетика и системный анализ, 2001, № 2, с. 132-144
[2] Sotskov Yu.N., Leontev V.K., Gordeev E.N. Some concepts of stability analysis in combinatorial optimization. Discrete Applied Mathematics, 1995, no. 58, рр. 169-190
[3] Гордеев Э.Н., Леонтьев В.К. Общий подход к исследованию устойчивости решений в задачах дискретной оптимизации. Журнал вычислительной математики и математической физики, 1996, № 36, с. 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. Amsterdam, 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 Algotithms. 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