Silně polynomiální algoritmus pro řešení dvoustranných lineárních soustav v max-algebře

Abstrakt

Je preyentován algoritmus pro řešení systémů (max,+)-lineárních rovnic velikosti mxn. Systémy mají proměnné na obou stranách rovnic.

Po O(m^4 n^4) iteracích algoritmus buď najde řešení systému, nebo zjistí, že řešení neexistuje. Každá iterace vyžaduje O(mn) operací, takže složitost uvedeného algoritmu je O(m^5n^5).

Klíčová slova

• strongly
• polynomial
• algorithm
• solving
• two-sided
• linear
• systems
• max-algebra