Ведущая научная школа
«Экстремальные задачи на дискретных структурах»

Область исследований — задачи математической кибернетики на дискретных структурах. Цель исследований — разработка математических методов и эффективных алгоритмов решения задач существования, построения и перечисления дискретных объектов на подобъекты более простой структуры и задач поиска экстремальных функций, заданных на дискретных множествах. Задача исследований — поддержать и сохранить достигнутый в настоящее время мировой уровень научных результатов коллектива.

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

© Институт математики им. С. Л. Соболева СО РАН, 2004