Комбинаторно-геометрические свойства полиэдров задач комбинаторной оптимизации Максименко Александр Николаевич

Краткое описание

Максименко, Александр Николаевич.
Комбинаторно-геометрические свойства полиэдров задач комбинаторной оптимизации : диссертация ... доктора физико-математических наук : 01.01.09 / Максименко Александр Николаевич; [Место защиты: Национальный исследовательский Нижегородский государственный университет им. Н.И. Лобачевского]. - Ярославль, 2019. - 250 с. : ил.
Оглавление диссертациидоктор наук Максименко Александр Николаевич
Оглавление

Введение
Краткое содержание работы

Глава 1. Основные понятия
1.1. Множества и графы
1.2. Многогранники
1.3. Сложность задач и алгоритмов
1.4. Задачи комбинаторной оптимизации

Глава 2. Многогранники задач
2.1. Многогранники и полиэдры задач
2.2. Задача идентификации грани
2.3. Характеристики графа многогранника
2.4. Гиперграни и расширение многогранника
2.5. Вопросы

Глава 3. Аффинная сводимость
3.1. Аффинная сводимость задач
3.2. Конусное разбиение пространства исходных данных
3.3. Сравнение многогранников
3.4. Аффинная сводимость многогранников

Глава 4. Примеры аффинной сводимости
4.1. Многогранники покрытий и двойных покрытий
4.2. Многогранники с NP-полным критерием несмежности вершин
4.3. Многогранники линейных порядков и деревьев Штейнера в графе
4.4. Многогранники c простым критерием смежности вершин
4.5. Многогранники задачи коммивояжера
3

4.6. Булевы многогранники степени p
4.7. Конусные разбиения для задачи о кратчайшем орпути
и для задачи о назначениях

Глава 5. Расширенная аффинная сводимость
5.1. Теория
5.2. Примеры
5.3. Аналог теоремы Кука для многогранников

Глава 6. Циклические многогранники
6.1. Определение и свойства
6.2. Компактная расширенная формулировка
6.3. Диаметр ридж-графа циклического многогранника

Глава 7. Алгоритмы прямого типа
7.1. Теория
7.2. Кликовое число для задачи о кратчайшем орпути
7.3. Примеры алгоритмов непрямого типа

Глава 8. Контрпримеры
8.1. Простые примеры
8.2. Сложность расширения и число прямоугольного покрытия
8.3. Другие комбинаторные характеристики

Заключение

Список литературы
4