Tropicalizing the simplex algorithm
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4147882 (Why is no real title available?)
- scientific article; zbMATH DE number 3906559 (Why is no real title available?)
- scientific article; zbMATH DE number 19091 (Why is no real title available?)
- scientific article; zbMATH DE number 3466805 (Why is no real title available?)
- scientific article; zbMATH DE number 3570223 (Why is no real title available?)
- scientific article; zbMATH DE number 1944711 (Why is no real title available?)
- scientific article; zbMATH DE number 5019906 (Why is no real title available?)
- scientific article; zbMATH DE number 2221693 (Why is no real title available?)
- scientific article; zbMATH DE number 3068536 (Why is no real title available?)
- -convexity
- A Field of Generalised Puiseux Series for Tropical Geometry
- A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
- A new decision method for elementary algebra
- Algorithms in real algebraic geometry
- An asymptotic simplex method for singularly perturbed linear programs
- Asymptotic Linear Programming
- Best approximation in max-plus semimodules
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Computing the vertices of tropical polyhedra using directed hypergraphs
- Criss-cross methods: A fresh view on pivot algorithms
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- Cyclic projectors and separation theorems in idempotent convex geometry
- Duality and separation theorems in idempotent semimodules.
- Duality theory for finite and infinite matroids with coefficients
- From Parity and Payoff Games to Linear Programming
- Idempotent functional analysis: An algebraic approach
- Introduction to max-linear programming
- Linear and combinatorial optimization in ordered algebraic structures
- Linear independence over tropical semirings and beyond
- Logarithmic limit sets of real semi-algebraic sets
- Maximal minors and their leading terms
- Minimal external representations of tropical polyhedra
- Minimal half-spaces and external representation of tropical polyhedra
- Minimax algebra
- New Lower Bounds for Convex Hull Problems in Odd Dimensions
- The complexity of mean payoff games on graphs
- The duality theorem for min-max functions
- The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)
- The number of extreme points of tropical polyhedra
- The tropical Grassmannian
- Tropical Cramer determinants revisited
- Tropical Polytopes and Cellular Resolutions
- Tropical convexity
- Tropical halfspaces
- Tropical linear-fractional programming and parametric mean payoff games
- Tropical polyhedra are equivalent to mean payoff games
Cited in
(38)- On a tropical dual Nullstellensatz
- Tropical spectrahedra
- Computing complex and real tropical curves using monodromy
- On Affine Tropical F5 Algorithms
- On tropical fractional linear programming
- Symmetric polynomials in tropical algebra semirings
- Bitangents to plane quartics via tropical geometry: rationality, \(\mathbb{A}^1\)-enumeration, and real signed count
- A note on resolving the inconsistency of one-sided max-plus linear equations.
- Weighted digraphs and tropical cones
- A tropical isoperimetric inequality
- Mustafin varieties, moduli spaces and tropical geometry
- A note on tropical linear and integer programs
- What Tropical Geometry Tells Us about the Complexity of Linear Programming
- Dynamic resource location with tropical algebra
- Tropical linear spaces and tropical convexity
- Tropical representations and identities of plactic monoids
- Monomial Tropical Cones for Multicriteria Optimization
- Abstract tropical linear programming
- Lifting tropical bitangents
- Minimizing maximum lateness in two-stage projects by tropical optimization
- Tropical Carathéodory with matroids
- Convergent Hahn series and tropical geometry of higher rank
- Submathematics and tropical mathematics
- Combinatorics and real lifts of bitangents to tropical quartic curves
- Log-Barrier Interior Point Methods Are Not Strongly Polynomial
- Tropical totally positive matrices
- The tropical double description method
- Face posets of tropical polyhedra and monomial ideals
- Tropicalization of facets of polytopes
- The complexity of tropical matrix factorization
- Solving mean-payoff games via quasi dominions
- Smoothed analysis of deterministic discounted and Mean-payoff games
- Approximating the volume of tropical polytopes is difficult
- Tropical Complementarity Problems and Nash Equilibria
- Signed tropicalization of polar cones
- Solving mean-payoff games via quasi dominions
- Morphological Perceptrons: Geometry and Training Algorithms
- Tropical planar networks
This page was built for publication: Tropicalizing the simplex algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453613)
