Алгоритм поиска решения переопределенной тропической линейной системы с помощью анализа стабильных точек подсистем

В данной статье доказывается, что для любой переопределенной линейной тропической системы найдется квадратная подсистема, такая, что ее стабильное решение будет решением исходной системы. Это позволяет построить простой алгоритм, решающий переопределенные тропические линейные системы с конечными целочисленными коэфициентами за время $O((C_m^nn ^2+n^3)M(N))$, где $m$ – количество уравнений, $n$ – количество переменных, а $M(N)$ – время арифметических операций с числами, не превосходящими максимальное число в матрице по модулю. Для слабопереопределенных систем это время работы полиномиально. Библ. – 10 назв.