Исследование задач целочисленной линейной оптимизации с ограниченным спектром миноров Грибанов, Дмитрий Владимирович

Короткий опис

Грибанов, Дмитрий Владимирович.Исследование задач целочисленной линейной оптимизации с ограниченным спектром миноров : диссертация ... кандидата физико-математических наук : 01.01.09 / Грибанов Дмитрий Владимирович; [Место защиты: Мат. ин-т им. В.А. Стеклова. С.-Петерб. отд-ние РАН]. - Нижний Новгород, 2016. - 87 с.

Оглавление диссертациикандидат наук Грибанов, Дмитрий Владимирович
Оглавление
Введение
1 Терминология, обозначения и конструктивные аналоги теоремы А. Хинчина
1.1 Терминология и обозначения
1.1.1 Множества и матрицы
1.1.2 Сведения из теории решеток
1.1.3 Полиэдры и политопы
1.1.4 Грани, вершины, фасеты
1.1.5 Постановка задачи ЦЛП
1.2 Аналоги теоремы А. Хинчина и их приложения
1.2.1 Ширина полиэдра и теорема А. Хинчина
1.2.2 Эффективный аналог теоремы А. Хинчина для полиэдров
1.2.3 Эффективный аналог теоремы А. Хинчина для симплексов
2 Задачи ЦЛП и вычисления ширины полиэдра в некоторых классах полиэдров
2.1 ЦЛП для некоторых классов полиэдров с ограниченными
минорами
2.1.1 Унимодулярная декомпозиция многогранного конуса
2.1.2 Специальный класс полиэдров
2.1.3 Постановка задачи ЦЛП через выпуклую оболочку точек
2.2 Эффективное вычисление ширины симплексов с
ограниченными минорами
3 Доказательства гипотез ограниченных миноров для
{0,1}-полиэдров трех задач на графах
3.1 Дополнительная терминология и дополнительные обозначения
3.1.1 Некоторые определения и обозначения теории графов
3.1.2 Некоторые классические задачи теории графов и их постановки
3.2 Задача о независимом множестве
3.2.1 Некоторое включение
3.2.2 Теорема Б. Рида
3.2.3 Основной результат этого раздела
3.3 Задача о вершинном доминирующем множестве
3.3.1 Вспомогательные результаты
3.3.2 Основной результат этого раздела
3.4 Задача о реберном доминирующем множестве
3.4.1 Кликовая ширина графов и ее значение
3.4.2 Основной результат этого раздела
Заключение
Литература