Доклад Протасова Владимира Юрьевича «Максимальный ацикличный подграф и устойчивость динамических систем»

На Большом семинаре лаборатории 26 марта Владимир Юрьевич Протасов сделал доклад на тему «Максимальный ацикличный подграф и устойчивость динамических систем».

Аннотация:

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

Часть результатов получены совместно с А.Цветковичем (институт Гран Сассо, Италия).