О ТРУДНО АППРОКСИМИРУЮЩИХСЯ КОММИВОЯЖЕРАХ И ИМЕННЫХ МЕДАЛЯХ ОТДЕЛЕНИЯ

Президиум УрО РАН 17 марта открыл доклад доктора физико-математических наук М.Ю. Хачая «Аппроксимируемость задачи о нескольких коммивояжерах». Задача коммивояжера — классический пример так называемой NP-трудной задачи, в общем виде не допускающей эффективной аппроксимируемости со сколько-нибудь приемлемой точностью, однако для частных случаев находятся достаточно эффективные приближенные алгоритмы. Михаил Юрьевич рассказал о ее расширении для «нескольких коммивояжеров», то есть решении проблемы построения наиболее экономичного плана обхода заданного множества клиентов («городов») несколькими обслуживающими устройствами («коммивояжерами»). Путем кластеризации множества клиентов удалось найти алгоритм, который находит приближенное решение задачи с наперед заданной точностью за время, ограниченное сверху полиномом от числа обслуживаемых клиентов. Это, подчеркнул докладчик, максимум, чего можно было ожидать. Существенная новизна полученных результатов состоит в том, что традиционно методы комбинаторной оптимизации применялись при решении задач теории обучения, но уральским ученым удалось, напротив, эффективно использовать кластеризацию для решения оптимизационной задачи. Выступивший в прениях по докладу академик В.И. Бердышев положительно отозвался о проделанной коллективом отдела математического программирования работе, отметив, что она является достойным продолжением традиций школы покойного академика И.И. Еремина.
Президиум одобрил проект постановления о проведении конкурса наград УрО РАН 2016 года. Уже в мае объединенные ученые советы и конкурсные комиссии должны будут рассмотреть заявки и провести голосование по кандидатурам на награждение шестью именными медалями (в области прикладных научных работ, физико-технических наук, биологии, экономики, медицинских и сельскохозяйственных наук) и девятью грамотами, а торжественное вручение пройдет на осеннем Общем собрании Отделения.Кроме того, был рассмотрен ряд оперативных вопросов.

Соб. инф.