Tropicalizing the simplex algorithm
classification
🧮 math.CO
math.OC
keywords
algorithmsimplextropicalanalogcombinatorialcomputationconstraintscosts
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.