SIAM Journal on Discrete Mathematics • Vol 29 • No 2
Tropicalizing the Simplex Algorithm
January 2015 • Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig
We develop a tropical analog of the simplex algorithm for linear programming.\nIn particular, we obtain a combinatorial algorithm to perform one tropical\npivoting step, including the computation of reduced costs, in O(n(m+n)) time,\nwhere m is the number of constraints and n is the dimension.\n