New algorithms for solving tropical linear systems
Alex Davydow · St Petersburg Mathematical Journal · 2017
The problem of solving tropical linear systems, a natural problem of tropical mathematics, has already proved to be very interesting from the algorithmic point of view: it is known to be in NP ∩ coN P , but no polynomial time algorithm is known, although counterexamples for existing pseudopolynomial algorithms are (and must be) very complex.In this work, the study of algorithms for solving tropical linear systems is continued.First, a new reformulation of Grigoriev's algorithm is presented, which brings it closer to the algorithm of Akian, Gaubert, and Guterman; this makes it possible to formulate a whole family of new algorithms, and, for some algorithms in this family, none of the known superpolynomial counterexamples work.Second, a family of algorithms for solving overdetermined tropical systems is presented.An explicit algorithm is exhibited in the paper that can solve a tropical linear system determined by an (m × n)-matrix with maximal element M in time Θ m n poly m, n, log M , and this time matches the complexity of the best of previously known algorithms for feasibility testing. §1. Introduction Tropical mathematics and tropical linear algebra.Tropical mathematics unites three closely related fields of study: tropical algebra, tropical analysis, and tropical geometry.The term is usually taken to mean mathematics obtained from classical mathematics by replacing the addition and multiplication operations with minimum and addition (respectively), hence the term min-plus algebra.Sometimes maximum is used instead of minimum, with perfectly symmetrical results, so in what follows we always use the minimum operation.Taking the minimum in tropical context is usually denoted by ⊕; addition is denoted by ⊗.The ⊕ operation is idempotent, i.e., a ⊕ a = a, so tropical mathematics is in fact a part of idempotent mathematics, although lately these notions have often been identified so that the term "tropical" is sometimes applied to any mathematical constructions with an idempotent operation.Tropical algebra was the first section of tropical mathematics to appear.The term originates from French mathematicians and first appeared in the 1980s.Although different authors attribute the term to different researchers [31,28,21], all sources agree that the term came into general use in the honor of one of the founders of this field, a Brazilian mathematician Imre Simon, so the term "tropical" simply means how French mathematicians viewed Brazil.Simon himself used the term already in the paper [30] that laid out the foundations of tropical algebra, attributing the term to Christian Choffrut.Initially, the term "tropical" was used for the discrete version of (min, + ) algebra, but at present the terminology has shifted, and tropical algebra is usually meant to be an algebra over the semifield R min (as stated above) or even, sometimes, an arbitrary 2010 Mathematics Subject Classification.Primary 30L10.