18 марта 2020 г.

Geometric theory of optimal control

Расписание: 

четверг, 16:45

Аудитория: 

Семинар проходит онлайн, в zoom, https://us06web.zoom.us/j/84704253405?pwd=M1dBejE1Rmp5SlUvYThvZzM3UnlvZz09

Докладчик: 

В.Ю. Протасов
МГУ, мехмат

Название: 

Максимальный ацикличный подграф и задача о ближайшей устойчивой системе

Аннотация доклада: 

Проблема MAS (Maximal Acyclic Subgraph) состоит в том, чтобы убрать наименьшее возможное число ребер заданного ориентированного графа, чтобы оставшийся граф не имел циклов. Это -- одна из классических NP-полных задач. В настоящее время не известно ни одного алгоритма, который давал бы ее приближенное решение с коэффициентом приближения большим 1/2 (коэффициент 1/2 получить легко). Оказывается, задача MAS тесно связана с задачей стабилизации системы -- задачей нахождения ближайшей устойчивой положительной динамической системы. Это позволяет применить задаче MAS методы из теории устойчивости линейных систем. Мы, в частности, увидим, что некоторая ослабленная версия MAS может быть решена явно даже для относительно больших графов, а для самой задачи MAS построим алгоритм, дающий хорошие численные результаты приближенного решения.

Доклад будет проходить онлайн по skype видеоконференции на msu.opu@gmail.com ("Геометрическое управлние")