Tropicalizing the Simplex Algorithm
From MaRDI portal
Publication:3453613
DOI10.1137/130936464zbMATH Open1334.14033arXiv1308.0454OpenAlexW2212625624WikidataQ117245046 ScholiaQ117245046MaRDI QIDQ3453613
Xavier Allamigeon, Stéphane Gaubert, Michael Joswig, Pascal Benchimol
Publication date: 27 November 2015
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1308.0454
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of mean payoff games on graphs
- Tropical convexity
- Linear independence over tropical semirings and beyond
- Linear and combinatorial optimization in ordered algebraic structures
- Minimax algebra
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)
- Tropical polyhedra are equivalent to mean payoff games
- Introduction to max-linear programming
- Tropical linear-fractional programming and parametric mean payoff games
- Algorithms in real algebraic geometry
- Duality and separation theorems in idempotent semimodules.
- Computing the vertices of tropical polyhedra using directed hypergraphs
- The tropical Grassmannian
- Logarithmic limit sets of real semi-algebraic sets
- Tropical Polytopes and Cellular Resolutions
- Idempotent functional analysis: An algebraic approach
- Minimal half-spaces and external representation of tropical polyhedra
- A new decision method for elementary algebra
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- Maximal minors and their leading terms
- A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
- The duality theorem for min-max functions
- Criss-cross methods: A fresh view on pivot algorithms
- Duality theory for finite and infinite matroids with coefficients
- -convexity
- An asymptotic simplex method for singularly perturbed linear programs
- Asymptotic Linear Programming
- The number of extreme points of tropical polyhedra
- From Parity and Payoff Games to Linear Programming
- Cyclic projectors and separation theorems in idempotent convex geometry
- Minimal external representations of tropical polyhedra
- A Field of Generalised Puiseux Series for Tropical Geometry
- Best approximation in max-plus semimodules
- Tropical Cramer determinants revisited
- New Lower Bounds for Convex Hull Problems in Odd Dimensions
Cited In (33)
- On a tropical dual Nullstellensatz
- Computing complex and real tropical curves using monodromy
- On Affine Tropical F5 Algorithms
- Tropical spectrahedra
- On tropical fractional linear programming
- Bitangents to plane quartics via tropical geometry: rationality, \(\mathbb{A}^1\)-enumeration, and real signed count
- Symmetric polynomials in tropical algebra semirings
- Weighted digraphs and tropical cones
- What Tropical Geometry Tells Us about the Complexity of Linear Programming
- Mustafin varieties, moduli spaces and tropical geometry
- 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
- Minimizing maximum lateness in two-stage projects by tropical optimization
- Lifting tropical bitangents
- 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
- Face posets of tropical polyhedra and monomial ideals
- Tropical totally positive matrices
- Solving Mean-Payoff Games via Quasi Dominions
- Tropicalization of facets of polytopes
- Solving mean-payoff games via quasi dominions
- The complexity of tropical matrix factorization
- A note on resolving the inconsistency of one-sided max-plus linear equations
- Tropical Complementarity Problems and Nash Equilibria
- Approximating the volume of tropical polytopes is difficult
- 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)
