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 Connect in order to contact the contributor
Submitted on : Tuesday, January 14, 2014 - 4:28:55 PM
Last modification on : Wednesday, February 2, 2022 - 3:53:50 PM

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