Tropicalizing the Simplex Algorithm
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig · SIAM Journal on Discrete Mathematics · 2015
We develop a tropical analogue 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.