RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Геометрическая теория оптимального управления
18 марта 2020 г. 16:45–18:20, г. Москва, Доклад будет проходить онлайн по skype видеоконференции на msu.opu@gmail.com ("Геометрическое управлние")
 


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

В. Ю. Протасов

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Количество просмотров:
Эта страница:28

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

Website: http://opu.math.msu.su/node/576

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020