Geometricheskie konstrukcii i slozhnost' v kombinatornoj optimizacii

Геометрические конструкции и сложность в комбинаторной оптимизации. Бондаренко В.А., Максименко А.Н. М.: ЛКИ, URSS. 2008. 182 с. ISBN 978-5-382-00687-1......Page 1
Оглавление......Page 3
Предисловие......Page 5
1. Введение......Page 8
1.1. Задачи и алгоритмы комбинаторной оптимизации......Page 8
1.2. Элементы теории выпуклых многогранников......Page 16
2. Алгоритмы, использующие линейные сравнения......Page 30
2.1. Унифицированная постановка задач......Page 30
2.2. Многогранники задач. Конусное разбиение......Page 35
2.3. Линейные разделяющие деревья......Page 37
2.4. Алгоритмы прямого типа......Page 44
3. Алгоритмы и многогранники конкретных задач......Page 50
3.1. Предварительные замечания......Page 50
3.2. Задачи сортировки, перестановочные многогранники......Page 51
3.3. Матроиды и «жадный» алгоритм......Page 71
3.4. Задача о кратчайшем пути......Page 79
3.5. Задачи о паросочетаниях......Page 84
3.6. Задача коммивояжера......Page 88
3.7. Другие труднорешаемые задачи......Page 100
4. Аффинная сводимость......Page 119
4.1. Граф полиэдрального разбиения......Page 119
4.2. Аффинная сводимость......Page 121
4.3. Задача о клике......Page 125
4.4. Задача коммивояжера......Page 127
4.5. Задача о трехмерном сочетании......Page 137
4.6. Задачи рюкзак и разбиение......Page 142
4.7. Задача о назначениях......Page 152
5. Многогранники с высокой плотностью графа......Page 155
5.1. Об одной гипотезе Д. Гейла......Page 155
5.2. К вопросу о полиномиальной разрешимости задач......Page 157
5.3. Корневые полуметрические многогранники......Page 160
Список литературы......Page 172