Tropicalizing the simplex algorithm
arXiv:1308.0454 · doi:10.1137/130936464
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.
v1: 35 pages, 7 figures, 4 algorithms; v2: improved presentation, 39 pages, 9 figures, 4 algorithms
References in corpus (4)
Cited by in corpus (22)
- Log-barrier interior point methods are not strongly polynomial
- Weighted digraphs and tropical cones
- Tropical spectrahedra
- A Tropical Approach to Neural Networks with Piecewise Linear Activations
- Solving generic nonarchimedean semidefinite programs using stochastic game algorithms
- Lifting tropical bitangents
- Temporal State Machines: Using temporal memory to stitch time-based graph computations
- Tropical totally positive matrices
- Mustafin varieties, moduli spaces and tropical geometry
- Approximating the Volume of Tropical Polytopes is Difficult
- Combinatorics and real lifts of bitangents to tropical quartic curves
- Linear programs and convex hulls over fields of Puiseux fractions
- Bitangents to plane quartics via tropical geometry: rationality, -enumeration, and real signed count
- Minimizing maximum lateness in two-stage projects by tropical optimization
- Symmetric Polynomials in Tropical Algebra Semirings
- Face posets of tropical polyhedra and monomial ideals
- Linear and Rational Factorization of Tropical Polynomials
- Convergent Hahn Series and Tropical Geometry of Higher Rank
- Signed tropical convexity
- Tropical analogues of a Dempe-Franke bilevel optimization problem
- Oriented Matroids from Triangulations of Products of Simplices
- The tropicalization of the entropic barrier