What Tropical Geometry Tells Us about the Complexity of Linear Programming
From MaRDI portal
Publication:5150211
DOI10.1137/20M1380211zbMath1459.90124MaRDI QIDQ5150211
Stéphane Gaubert, Pascal Benchimol, Xavier Allamigeon, Michael Joswig
Publication date: 10 February 2021
Published in: SIAM Review (Search for Journal in Brave)
linear programmingcentral pathtropical geometrystrongly polynomial complexitycontinuous analogue of the Hirsch conjecture
Linear programming (90C05) Interior-point methods (90C51) Foundations of tropical geometry and relations with algebra (14T10) Tropical optimization (e.g., max-plus optimization) (90C24)
Related Items
The polyhedral geometry of truthful auctions, Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria, The Gaussian entropy map in valued fields, Asymmetric tropical distances and power diagrams
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Information geometry and interior-point algorithms in semidefinite programs and symmetric cone programs
- Handbook of Hilbert geometry
- An update on the Hirsch conjecture
- Minimal half-spaces and external representation of tropical polyhedra
- The central curve in linear programming
- A new polynomial-time algorithm for linear programming
- Polytopes and arrangements: diameter and curvature
- Exponential behaviour of the Butkovič-Zimmermann algorithm for solving two-sided linear systems in max-algebra
- A polynomial-time algorithm, based on Newton's method, for linear programming
- Interior path following primal-dual algorithms. I: Linear programming
- A polynomial-time algorithm for a class of linear complementarity problems
- On the complexity of following the central path of linear programs by linear extrapolation. II
- Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals
- A modified layered-step interior-point algorithm for linear programming
- A primal-dual interior point method whose running time depends only on the constraint matrix
- Duality and separation theorems in idempotent semimodules.
- Tropical convexity
- Who solved the Hirsch conjecture?
- Tropical spectrahedra
- Solving generic nonarchimedean semidefinite programs using stochastic game algorithms
- A strongly polynomial algorithm for solving two-sided linear systems in max-algebra
- On the curvature of the central path of linear programming theory
- Patchworking algebraic curves disproves the Ragsdale conjecture
- Linear Programs and Convex Hulls Over Fields of Puiseux Fractions
- A Simple Variant of the Mizuno--Todd--Ye Predictor-Corrector Algorithm and Its Objective-Function-Free Complexity
- The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- A Field of Generalised Puiseux Series for Tropical Geometry
- Non-archimedean amoebas and tropical varieties
- Tropicalizing the Simplex Algorithm
- Central Path Curvature and Iteration-Complexity for Redundant Klee—Minty Cubes
- The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
- The real field with convergent generalized power series
- On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
- A Variant of the Vavasis--Ye Layered-Step Interior-Point Algorithm for Linear Programming
- Log-Barrier Interior Point Methods Are Not Strongly Polynomial
- Enumerative tropical algebraic geometry in ℝ²
- Asymptotic Linear Programming
- -convexity
- Logarithmic limit sets of real semi-algebraic sets
- Monomial Tropical Cones for Multicriteria Optimization
- A Friendly Smoothed Analysis of the Simplex Method
- A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
- Algebraic and Topological Tools in Linear Optimization
- Combinatorial Simplex Algorithms Can Solve Mean Payoff Games
- On the total curvature of tropical hypersurfaces
- NEWTON FLOW AND INTERIOR POINT METHODS IN LINEAR PROGRAMMING
- Tropical Polytopes and Cellular Resolutions
- The Logarithmic Limit-Set of an Algebraic Variety
- Tropical algebraic geometry
