Введение к работе
Актуальность темы. Задачи аппроксимации графов ЯВЛЯЮТСЯ QjfJT^C кватными моделями имеющих широкие приложения задач кластеризации и классификации взаимосвязанных объектов, cL наследственными системами являются множества допустимых решений большого числа сложных практически важных задач. Задачи аппроксимации графов и наследственных систем в общем случае относятся к классу NP-трудных, поэтому актуальным направлением исследований является разработка алгоритмов приближенного решения этих задач и получение гарантированных оценок точности алгоритмов. В последнее десятилетие исследования указанных задач активно ведутся в России и за рубежом.
Цель работы. Целью НсІСТОЯЩбИ ДИССертаЦИИ ЯІВЛЯІЄТСЯ ИССЛбДОВВіНИб различных вариантов задачи аппроксимации графа и ее обобщений — задач аппроксимации наследственных систем, а также разработка и анализ приближенных алгоритмов решения этих задач.
Методы исследований. При выполнении работы использовались методы теории графов, теории матроидов, дискретной оптимизации, методы анализа алгоритмов в худшем случае.
Научная новизна. В диссертационной работе предложены новые полиномиальные алгоритмы приближенного решения различных вариантов задачи аппроксимации графа. Получены гарантированные оценки точности предложенных алгоритмов. Исследованы различные постановки более общей задачи аппроксимации наследственных систем, найдены оценки аппроксимационной сложности наследственных систем. Рассмотрена новая постановка задачи аппроксимации графа. Доказано, что в общем случае эта задача является NP-трудной, найдены полиномиально разрешимые случаи.
Основные результаты. 1. Для задачи аппроксимации графами, имеющими не более k компонент связности, предложен алгоритм локального улучшения. Для любого фиксированного k ^ 2 доказано, что алгоритм локального улучшения гарантированно асимптотически точен на семействе неплотных графов. На основе этого алгоритма построена полиномиальная приближенная CXeiVl cL решения ЗсїД^сїіЧИ HQj неплотных графах. Для
сти, предложен приближенный алгоритм с достижимой гарантированной оценкой точности.
2. Для задачи аппроксимации линейной наследственной системы, яв- ляющеи СЯ обобщением задачи аппроксимации графа, доказана достижимая оценка аппроксимационной сложности. Исследованы другие постановки задачи аппроксимации наследственных систем, связанные с оптимизационными задачами. Для двух вариантов задачи получены оценки аппроксимационной сложности наследственных систем, которые можно рассматривать как гарантированные оценки точности алгоритмов приближенного решения задач о максимальном независимом и о минимальном зависимом множестве наследственной системы.
3. Рассмотрена новая постановка задачи аппроксимации графами с компонентами связности ограниченного размера. 13 Ы Д 6 Jl 6Н ы полиномиально разрешимые случаи. Доказано, что задача аппроксимации графами, мощности компонент связности которых не превосходят p, является NР-трудной для любого фиксированного p ^ 3. Для случая p = 3 предложен алгоритм приближенного решения задачи и получена гарантированная оценка его точности.
Практическая и теоретическая ценность. Полученные в диссертации теоретические результаты применимы в научных исследованиях, а также в учебном процессе. Предложенные алгоритмы могут быть использованы при решении задач достаточно большой размерности.
Апробация работы. Основные результаты диссертации ДОКЛ ЕДЫ В E ЛИСЬ Hct III-V Всероссийских конференциях «Проблемы оптимизации и экономические приложения» (Омск, 2006, 2009, 2012); 39-й Всероссийской молодежной конференции «Проблемы теоретической и прикладной математики» (Екатеринбург, 2008); VIII Международной научной конференции «Дискретные модели в теории управляющих систем» (Москва, 2009); X Международном семинаре «Дискретная математика и ее приложения» (Москва, 2010); XIV Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 2011), а также на научных семинарах в Омском государственном университете им. Ф.М. Достоевского, в Институте математики им. С. Jl. Соболева СО РАН и его Омском филиале.
Публикации. По теме диссертации автором опубликовано 14 научных работ, из них 3 в рецензируемых изданиях из списка ВАК. Конфликта интересов с соавторами нет, в совместных работах соискателю принадлежат идеи доказательств результатов, включенных в диссерта-
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы, содержащего 59 наименований. Общий объем работы 90 С T р QjH И T T^
