Tropicalizing the simplex algorithm
arXiv:1308.0454 · doi:10.1137/130936464
Abstract
We develop a tropical analog of the simplex algorithm for linear programming. In particular, we obtain a combinatorial algorithm to perform one tropical pivoting step, including the computation of reduced costs, in O(n(m+n)) time, where m is the number of constraints and n is the dimension.
v1: 35 pages, 7 figures, 4 algorithms; v2: improved presentation, 39 pages, 9 figures, 4 algorithms