Skip to Main content Skip to Navigation
Journal articles

Tropicalizing the simplex algorithm

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.
Complete list of metadata
Contributor : Pascal Benchimol <>
Submitted on : Tuesday, January 14, 2014 - 4:28:55 PM
Last modification on : Monday, December 28, 2020 - 10:22:04 AM

Links full text




Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig. Tropicalizing the simplex algorithm. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2015, 29 (2), ⟨10.1137/130936464⟩. ⟨hal-00930913⟩



Record views