Tropicalizing the Simplex Algorithm
From MaRDI portal
Publication:3453613
DOI10.1137/130936464zbMath1334.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)
Full work available at URL: https://arxiv.org/abs/1308.0454
Related Items
Weighted digraphs and tropical cones, Log-Barrier Interior Point Methods Are Not Strongly Polynomial, Tropicalization of facets of polytopes, Bitangents to plane quartics via tropical geometry: rationality, \(\mathbb{A}^1\)-enumeration, and real signed count, On tropical fractional linear programming, Abstract tropical linear programming, Tropical Carathéodory with matroids, Tropical Complementarity Problems and Nash Equilibria, Monomial Tropical Cones for Multicriteria Optimization, Convergent Hahn series and tropical geometry of higher rank, Combinatorics and real lifts of bitangents to tropical quartic curves, Face posets of tropical polyhedra and monomial ideals, Solving mean-payoff games via quasi dominions, Tropical linear spaces and tropical convexity, Symmetric polynomials in tropical algebra semirings, What Tropical Geometry Tells Us about the Complexity of Linear Programming, Tropical spectrahedra, Solving Mean-Payoff Games via Quasi Dominions, Lifting tropical bitangents, Approximating the volume of tropical polytopes is difficult, Tropical totally positive matrices, Submathematics and tropical mathematics, A note on resolving the inconsistency of one-sided max-plus linear equations, Mustafin varieties, moduli spaces and tropical geometry, Tropical representations and identities of plactic monoids, Tropical planar networks, Computing complex and real tropical curves using monodromy, Morphological Perceptrons: Geometry and Training Algorithms, Minimizing maximum lateness in two-stage projects by tropical optimization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tropical linear-fractional programming and parametric mean payoff games
- The number of extreme points of tropical polyhedra
- Minimal half-spaces and external representation of tropical polyhedra
- Best approximation in max-plus semimodules
- A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
- Duality theory for finite and infinite matroids with coefficients
- Linear and combinatorial optimization in ordered algebraic structures
- Minimax algebra
- The complexity of mean payoff games on graphs
- Criss-cross methods: A fresh view on pivot algorithms
- Duality and separation theorems in idempotent semimodules.
- Maximal minors and their leading terms
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- An asymptotic simplex method for singularly perturbed linear programs
- The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)
- Tropical convexity
- Computing the vertices of tropical polyhedra using directed hypergraphs
- Minimal external representations of tropical polyhedra
- Cyclic projectors and separation theorems in idempotent convex geometry
- A new decision method for elementary algebra
- TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES
- Tropical Cramer determinants revisited
- A Field of Generalised Puiseux Series for Tropical Geometry
- Linear independence over tropical semirings and beyond
- From Parity and Payoff Games to Linear Programming
- Introduction to max-linear programming
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- The duality theorem for min-max functions
- New Lower Bounds for Convex Hull Problems in Odd Dimensions
- Asymptotic Linear Programming
- -convexity
- The tropical Grassmannian
- Logarithmic limit sets of real semi-algebraic sets
- Tropical Polytopes and Cellular Resolutions
- Algorithms in real algebraic geometry
- Idempotent functional analysis: An algebraic approach
