Название: Геометрические конструкции и сложность в комбинаторной оптимизации
Автор: Бондаренко В.А., Максименко А.Н.
Издательство: М.: ЛКИ, URSS
Год: 2008
Страниц: 182
Формат: djvu
Размер: 10,9 Мб
Язык: Русский

В задачах дискретной оптимизации, в общем случае, необходимо отыскать оптимальный объект среди конечного или, возможно, бесконечного счетного множества. В книге изучается аффинная сводимость задач — аналог сводимости в смысле Кука-Карпа. Исследуются геометрические свойства задач комбинаторной оптимизации, которые отражают их вычислительную сложность, приводятся оценки плотности полиэдральных графов задач, которые служат нижней границей временной трудоемкости алгоритмов из широкого класса, включающего большинство известных комбинаторных методов. Эта работа объединяет полученные за последние десять лет результаты, направленные на выяснение причин, препятствующих построению эффективных алгоритмов для большинства задач комбинаторной оптимизации. Книга представляет интерес для студентов, аспирантов, научных работников, специализирующихся в области вычислительной математики.