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

https://hal.inria.fr/hal-00930913
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

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

524