Об исследовании устойчивости задач на матроидах
УДК 004.056:519.854
Об исследовании устойчивости задач на матроидах
© Э.Н. Гордеев
МГТУ им. <...> Н.Э. Баумана, Москва, 105005, Россия
За последние двадцать лет появились десятки статей, посвященных исследованию
устойчивости в задачах оптимизации, при этом многие результаты, опубликованные в отечественных научных журналах в 1970–1980-е годы, игнорируются, а
более поздние публикации цитируются как базовые и оригинальные. <...> Цель данной
статьи — обратить на это внимание на одном примере — исследование устойчивости в задачах на матроидах. <...> Для случая нормы Чебышева в пространстве возмущений параметров задачи проблема устойчивости всесторонне изучена в работах 1980-х годов, на которые авторы публикаций 1990-х и более поздних годов
вообще не ссылаются. <...> Для случая метрики l1 задача является технически более
сложной, поэтому нельзя говорить о полной эквивалентности опубликованных
ранее результатов и появившихся позднее. <...> При этом область теории матроидов взята просто в качестве примера. <...> Ключевые слова: оптимизационные задачи на матроидах, радиус устойчивости,
алгоритм исследования устойчивости. <...> В работах [1–7] рассматривались различные подходы к исследованию устойчивости в задачах дискретной оптимизации. <...> В одностраничных тезисах [8] для задачи о кратчайшем остове приведена постановка проблемы устойчивости решения задачи и сформулирован результат, касающийся простого случая одноэлементных
возмущений (без доказательств). <...> Задачи на матроидах исследованы в работах [1] и [6] для разных
классов метрик, типов функционалов и способов возмущения параметров задач. <...> Частичный обзор основных результатов приведен
и в [2]. <...> Э.Н. Гордеев
В [1–7] используются следующие терминология и обозначения. <...> На каждой траектории определяется функционал A — длина траектории
при взвешивании A, например линейный функционал
A
a j. <...> (1)
e j
Под дискретной оптимизационной задачей будем понимать <...>