Введение к работе
Актуальность темы. Наследственные системы - это универсальные комбинаторные объекты, сочетающие в себе черты систем независимости (систем подмножеств конечного множества, обладающих свойством наследственности) и систем множеств с аналогичным свойством наследственности "вверх". Задачи оптимизации и аппроксимации на наследственных системах являются математическими моделями множества сложных в вычислительном плане практически важных задач. Оптимизационные задачи на наследственных системах, как правило, являются ЖР-трудными.
Следующие три подхода к исследованию и решению ЖР-трудных задач оптимизации являются общепринятыми [3]: 1) разработка точных методов неявного перебора; 2) выделение полиномиально разрешимых классов подзадач; 3) построение приближенных полиномиальных алгоритмов с оценками точности получаемых решений.
В диссертационной работе в основном реализуется последний подход. Главным направлением исследований является разработка и анализ приближенных алгоритмов решения ЖР-трудных оптимизационных задач на наследственных системах, получение априорных оценок погрешности таких алгоритмов, в частности, жадных эвристик, а также изучение структуры и свойств наследственных систем.
В последние десятилетия большое развитие получила теория матро-идов - наследственных систем специального вида. Предложено достаточно много различных аксиоматизаций матроидов, детально изучены структура и свойства матроидов разных классов. Подробно рассмотрены оптимизационные задачи на матроидах и их пересечениях. Однако, на практике матроиды встречаются довольно редко, допустимыми множествами большей части задач комбинаторной оптимизации являются семейства независимых и зависимых множеств наследственных систем. И если оптимизационные задачи на системах независимости рассматривались в литературе достаточно часто, то задачи, множествами допустимых решений которых являются семейства зависимых множеств наследственных систем, изучены гораздо меньше. Недостаточно по сравнению с матроидами исследованы также структура и комбинаторные свойства наследственных систем.
На фоне бурного развития теории матроидов наблюдается также рост интереса к жадным алгоритмам (см., например, [20]). Это объясняется тем, что в ряде случаев жадный алгоритм имеет максимальную точность
в классе полиномиальных алгоритмов [29], либо является асимптотически точным алгоритмом [6].
Цель работы. Целью работы является исследование структуры наследственных систем и их частных случаев - наследственных систем графов и коматроидов (наследственных систем, дополнительных к матро-идам), изучение свойств целевых функций и приближенное решение оптимизационных задач на наследственных системах, матроидах и кома-троидах. Подробно исследованы задачи оптимизации аддитивных функций на наследственных системах и задачи минимизации супермодулярных функций на матроидах и коматроидах, а также их частные случаи -задача о р-медиане и задача аппроксимации графа. Особое внимание уделяется получению гарантированных оценок погрешности жадных алгоритмов и отысканию классов задач, разрешимых жадными алгоритмами.
Методы исследований. В работе использовались методы дискретной оптимизации, теории графов, теории матроидов, элементы теории решеток, методы анализа алгоритмов в худшем случае, а также новые методы построения гарантированных оценок погрешности алгоритмов, разработанные автором.
Научная новизна. В диссертационной работе даны новые определения наследственных систем и их частных случаев - коматроидов. Исследована структура и получены новые свойства этих объектов. Предложены новые алгоритмы приближенного решения задач комбинаторной оптимизации на наследственных системах. Получены гарантированные оценки погрешности этих алгоритмов и новые гарантированные оценки погрешности известных алгоритмов приближенного решения оптимизационных задач на наследственных системах.
Основные результаты. 1. Исследована структура наследственных систем и их частных случаев - коматроидов. Предложены различные аксиоматизации коматроидов. Получена характеризация графов циклов коматроидов и целочисленных полиматроидов.
-
Дано новое эквивалентное определение наследственной системы в терминах замыкания. Для наследственных систем графов доказан аналог теоремы Биркгофа-Уитни о представлении геометрических решеток. Доказана теорема, устанавливающая связь между коматроидами и решетками, двойственными геометрическим.
-
Получена гарантированная оценка погрешности жадного алгоритма в терминах параметров допустимой области и целевой функции задачи максимизации аддитивной функции на наследственной системе, уточ-
няющая известную оценку Дженкинса-Корте-Хаусмана. Предложена ха-рактеризация класса целевых функций задач на матроидах, разрешимых жадным алгоритмом, и доказано обобщение теоремы Радо-Эдмондса для задачи максимизации функции из этого класса.
-
Аналогичные оценки доказаны для задачи минимизации аддитивной функции на наследственной системе. Как следствие получены оценки погрешности обратного жадного алгоритма для задачи о минимальном двусвязном остовном подграфе и задачи о наименьшей раскраске графа. Установлена эквивалентность задачи минимизации аддитивной функции на наследственной системе и задачи о минимальном покрытии множества.
-
Получены оценки погрешности обратного жадного алгоритма для задачи минимизации невозрастающей супермодулярной функции на ко-матроиде. Как следствие получены оценки погрешности этого алгоритма для общей задачи о р-медиане на минимум. Исследована задача минимизации неубывающей супермодулярной функции на матроиде, к которой сведена известная задача аппроксимации графа.
-
Предложена постановка задачи матроидной аппроксимации, частным случаем которой является задача аппроксимации графа. Получена оценка аппроксимационной сложности графа для одного варианта задачи аппроксимации графа. Доказано, что задача аппроксимации графами с заданным числом компонент связности ЖР-трудна.
-
Предложены алгоритмы приближенного решения задачи аппроксимации графа, получены гарантированные оценки погрешности этих алгоритмов. Показано, что жадный алгоритм является гарантированно асимптотически точным алгоритмом аппроксимации неплотных графов. Доказано существование полиномиальной приближенной схемы для одного варианта задачи.
Практическая и теоретическая ценность. Работа имеет теоретический характер. Проведенные в диссертации исследования структуры множеств допустимых решений и свойств целевых функций общих задач дискретной оптимизации на наследственных системах, анализ приближенных алгоритмов их решения могут оказаться полезными при разработке или повышении эффективности алгоритмов приближенного решения конкретных оптимизационных задач, которые являются частными случаями оптимизационных задач на наследственных системах. Предложенные приближенные алгоритмы могут быть применены для решения практических задач достаточно большой размерности.
Теоретические результаты диссертации используются в учебном процессе в Омском государственном университете.
Апробация работы. Результаты диссертации прошли апробацию на VIII XIII Всероссийских конференциях "Математическое программирование и приложения" (Екатеринбург, 1993, 1995, 1997, 1999, 2003, 2007); X - XIV Международных Байкальских школах-семинарах "Методы оптимизации и их приложения" (Иркутск, Северобайкальск, 1995, 1998, 2001, 2005, 2008); II Сибирском конгрессе по прикладной и индустриальной математике (Новосибирск, 1996); II школе по теории графов (Новосибирск, 1997); I IV Всероссийских конференциях "Проблемы оптимизации и экономические приложения" (Омск, 1997, 2003, 2006, 2009); 18th IFIP Conference "System Modelling and Optimization" (Detroit, USA, 1997); International Conference on Operations Research (Zurich, Switzerland, 1998); Международной Сибирской конференции по исследованию операций (Новосибирск, 1998); Российских конференциях "Дискретный анализ и исследование операций" (Новосибирск, 2000, 2002); II International Workshop "Discrete Optimization Methods in Production and Logistics" (Omsk-Irkutsk, 2004); IX Международном семинаре "Дискретная математика и ее приложения" (Москва, 2007); Российской конференции "Дискретная оптимизация и исследование операций" (Владивосток, 2007), VIII Международной конференции "Дискретные модели в теории управляющих систем" (Москва, 2009), Международной научной конференции "Дискретная математика, алгебра и их приложения" (Минск, Беларусь, 2009), а также на научных семинарах в Институте математики им. С.Л. Соболева СО РАН, в его Омском филиале и в Уральском государственном университете.
Публикации. По теме диссертации автором опубликовано 28 статей, из них 9 статей - в журналах из списка ВАК. Конфликт интересов с соавторами отсутствует, в совместных работах соискателю принадлежат ключевые идеи доказательств результатов, включенных в диссертацию.
Структура и объем работы. Диссертация изложена на 217 страницах, состоит из введения, четырех глав, заключения и списка литературы, содержащего 130 наименований.
