|
|
Задачи дифференциальных уравнений, анализа и управления: теория и приложения
17 февраля 2020 г. 18:30–20:00, г. Москва, МГУ им. М.В. Ломоносова, механико-математический факультет, ауд. 13-06
|
|
|
|
|
|
Проблема максимального ацикличного подграфа и устойчивость линейных динамических систем
В. Ю. Протасовab a Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
b Факультет компьютерных наук, Национальный исследовательский университет «Высшая школа экономики»
|
Количество просмотров: |
Эта страница: | 172 |
|
Аннотация:
Проблема MAS (Maximal Acyclic Subgraph) состоит в устранении всех циклов данного ориентированного графа путем вычеркивания наименьшего возможного числа его ребер. Данная проблема является NP полной. В настоящее время не известно ни одного алгоритма, который давал бы ее приближенное решение с коэффициентом приближения большим 1/2 (коэффициент 1/2 получить легко). Мы свяжем MAS с задачей нахождения ближайшей устойчивой положительной динамической системы (задача стабилизации системы). Это позволит применить методы из теории устойчивости линейных систем к задаче MAS. Мы, в частности, увидим, что некоторая ослабленная версия задачи MAS может быть решена явно даже для относительно больших графов, а для самой задачи MAS построим алгоритм, дающий хорошие численные результаты.
|
|