Алексей Давыдов

Контрпример к алгоритму Григорьева

На семинаре будет рассмотрена задача о решении линейных тропических систем. Несмотря на то, что задача была поставлена достаточно давно до сих пор неизвестно полиномиальных решений для нее. Один из известных псевдополиномиальных алгоритмов для решения данной задачи - алгоритм Григорьева. На семинаре будет рассмотрена серия матриц, на которых алгоритм работает экспоненциальное время.