Семинар проводится совместно кафедрой дискретной математики ФИВТ МФТИ, кафедрой математических основ управления ФУПМ МФТИ и кафедрой высшей математики МФТИ.
На заседаниях семинара обсуждаются задачи современной комбинаторики, дискретной геометрии, теории кодирования, теории алгоритмов и др., а также их приложения.
Расписание семинаров доступно здесь.
На следующем семинаре 26 февраля состоится выступление А.Н. Максименко
"Комбинаторные свойства многогранников задач комбинаторной оптимизации"
Примерами задач комбинаторной оптимизации с линейной целевой функцией являются задача о кратчайшем пути, задача коммивояжера, задача о рюкзаке и многие другие. Каждая такая задача может быть естественным образом переформулирована в виде задачи линейного программирования, область допустимых решений которой представляет собой выпуклый многогранник. С одной стороны, такая интерпретация позволяет использовать для решения этих задач геометрические методы. С другой стороны, и именно об этом и пойдет речь в докладе, этот подход позволяет выявить комбинаторно-геометрические свойства задач, отделяющие (почти во всех известных случаях) полиномиально разрешимые задачи от NP-трудных.
