"Записки научных семинаров ПОМИ"
Том 402, стр. 69-82
Оценки сложности алгоритма Григорьева для решения тропических линейных систем
А. П. Давыдов
Академический Университет РАН,
ул. Хлопина, 8, корп. 3,
Санкт-Петербург 194021,
Россия
adavydow@yandex.ru
- Аннотация: Исследуется алгоритм решения целочисленных
тропических линейных систем, предложенный Д.~Ю.~Григорьевым в 2010 году.
В работе впервые получена неполиномиальная нижняя оценка на время
работы
этого алгоритма, а также улучшена известная
верхняя оценка.
Библ. -- 6 назв.
- Ключевые слова: тропические линейные системы, алгоритм Григорьева
[tropical lineear systems, Grigoriev's algorithm]
Полный текст(.pdf)