"Записки научных семинаров ПОМИ"

Том 450 , стр. 43-61

С.-Петербургский национальный исследовательский Академический университет Российской академии наук (СПбАУ РАН)

adavydow@gmail.com

Аннотация: В данной статье доказывается, что для любой переопределенной линейной тропической системы найдется квадратная подсистема, такая, что ее стабильное решение будет решением исходной системы. Это позволяет построить простой алгоритм, решающий переопределенные тропические линейные системы с конечными целочисленными коэфициентами за время $O((C_m^n n ^ 2 + n ^ 3) M(N))$, где $m$ -- количество уравнений, $n$ -- количество переменных, а $M(N)$ -- время арифметических операций с числами, не превосходящими максимальное число в матрице по модулю. Для слабопереопределенных систем это время работы полиномиально. Библ. -- 10 назв.
Ключевые слова: тропические линейные системы, слабопереопределенные тропические линейные системы [tropical linear system, weekly overdetermined tropical linear system]