Институт вычислительной математики и математической геофизики СОРАН

Пятая азиатская международная школа-семинар "Проблемы оптимизации сложных систем"

Кыргызская Республика, г.Бишкек, база "Эдельвейс" Иссык-Кульского Государственного Университета, 12 - 22 августа.
ВАЖНАЯ ИНФОРМАЦИЯ

Тезисы докладов

Как строить приближенные схемы для труднорешаемых задач оптимизации.

Кононов А.В.

Институт математики им. С.Л. Соболева СО РАН (Новосибирск)

Создание приближенных алгоритмов, возможно, самое популярное направление исследования в комбинаторной оптимизации и исследовании операций в последние два десятилетия. Как известно, все действительно интересные задачи трудны для решения. Это в особенности верно для задач комбинаторной оптимизации, где труднорешаемые (NP-трудные) задачи встречаются на каждом шагу. Поэтому для решения NP-трудных задач исследователи строят приближенные алгоритмы, в надежде найти решения близкие к оптимальным. Приближенные схемы – это субоптимальные методы, про которые можно доказать, что они быстро находят решение высокого качества. В нашем докладе мы обсудим и детально объясним базовые идеи, основные инструменты и стандартные подходы для построения таких схем. Доклад основан на главе Схурман и Вегингера «Приближенные схемы - учебник» из книги «Лекции по теории расписаний».

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]

© 2009, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 1996-2009, Сибирское отделение Российской академии наук, Новосибирск
Дата последней модификации: 06-Jul-2012 (11:52:52)