Задачи оптимизации и аппроксимации на наследственных системах

• Автор: Ильев, Виктор Петрович
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2010
• Место защиты: Омск
• Количество страниц: 217 с. : ил.

Оглавление
Введение

1. Наследственные системы, матроиды и коматроиды

1.1. Основные понятия

1.2. Наследственные системы целочисленных векторов

1.3. Наследственные системы и графы

1.3.1. Графы баз и циклов

1.3.2. Наследственные системы графов

1.4. Наследственные системы и решетки

1.4.1. Определение наследственной системы в терминах

замыкания
1.4.2. Решетки замкнутых множеств наследственных систем
1.4.3. Решетки открытых множеств коматроидов
2. Задачи оптимизации на наследственных системах, матроидах и коматроидах
2.1. Постановки задач
2.2. Задачи на наследственных системах с аддитивными целевыми функциями
2.2.1. Теорема Радо-Эдмондса и ее аналог для коматроидов
2.2.2. Оценки погрешности жадных алгоритмов для задач
на наследственных системах
2.2.3. Примеры
2.2.4. Эквивалентность задачи о минимальном зависимом
множестве и задачи о покрытии множества

2.3. Оценки погрешности жадных алгоритмов в терминах допустимой области и целевой функции
2.3.1. Уточнение оценки Дженкинса-Корте-Хаусмана
2.3.2. Оценка погрешности обратного жадного алгоритма
2.4. Задачи с неаддитивными целевыми функциями
2.4.1. Обобщения теоремы Радо-Эдмондса
2.4.2. Задачи, разрешимые жадным алгоритмом
3. Минимизация супермодулярных функций на матроидах
и коматроидах
3.1. Задачи минимизации супермодулярных функций
3.1.1. Постановки задач и известные результаты
3.1.2. Обобщения понятия супермодулярной функции
3.1.3. Свойства супермодулярных функций
3.2. Оценки погрешности обратного жадного алгоритма минимизации невозрастающей супермодулярной функции
3.2.1. Оценки в терминах параметров целевой функции
и допустимой области
3.2.2. Оценки погрешности обратного жадного алгоритма
в терминах параметров целевой функции
3.2.3. Апостериорная оценка
3.3. Следствия для задачи о р-медиане на минимум
3.4. Минимизация неубывающих супермодулярных функций
4. Задачи аппроксимации наследственных систем
4.1. Задачи матроидной аппроксимации
4.2. Задачи аппроксимации графов
4.2.1. Постановки задач
4.2.2. Оценка аппроксимационной сложности графа
4.3. Задача аппроксимации линейной наследственной системы
4.4. Вычислительная сложность задач аппроксимации графов .
4.4.1. Взвешенная задача

4.4.2. Невзвешенные задачи
4.5. Приближенное решение задачи аппроксимации графа .
4.5.1. Оценка погрешности жадного алгоритма для задачи аппроксимации графа
4.5.2. Гарантированно асимптотически точный алгоритм и полиномиальная приближенная схема
4.5.3. Алгоритмы с константными оценками точности
Заключение
Литература

Теорема 1.3. Пусть 9 — наследственная система.
1.5 — матроид тогда и только тогда, когда двойственная по Уитни система 9* является матроидом;
2. 9 — коматроид тогда и только тогда, когда двойственная система 9° является коматроидом.
Доказательство. Первое утверждение — хорошо известный из теории матроидов факт [127]. Второе следует из утверждения (С') теоремы
1.2, так как указанное в (С') свойство выполняется не только для циклов коматроида, но и для их дополнений. ■
В следующей теореме устанавливается связь между двойственными наследственными системами разных типов.
Теорема 1.4. Для любой наследственной системы 9 1. (9*)' = (9')°; 2. (9е)' = (£')*•
Доказательство. Рассмотрим произвольную наследственную систему <9 = (и, В) = {и, С), где В и С — семейства баз и циклов, соответственно.
1. Докажем первое равенство. По определению базами двойственной по Уитни системы <9* = {и, В*) являются всевозможные множества вида В* = и В, где В Є В, а по определению дополнительной системы циклами системы (5*)' являются множества вида 17 В*, где В* Є В*. Но {и В* : В* Є В*} = (В*)* — В. Таким образом, семейство баз наследственной системы 9 совпадает с семейством циклов системы (У)7.
В то же время по определению дополнительной системы циклами системы 9' — {и, С) являются множества вида С' = II В, где В Е В, а по определению двойственной системы циклами наследственной системы (9')° являются всевозможные множества вида и С', где С' Є С. Но {и С' : С' Е С'} = (В')' = В. Таким образом, семейство баз наследственной системы 9 совпадает с семейством циклов системы (9')°.