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

Оглавление
Введение
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. Алгоритмы с константными оценками точности . .
Заключение
Литература