What Tropical Geometry Tells Us about the Complexity of Linear Programming

DOI10.1137/20M1380211MaRDI QIDQ5150211zbMATH OpenFDO

Authors Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig

Publication date 10 February 2021

Published in SIAM Review (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/20M1380211

zbMATH Keywords

central pathcontinuous analogue of the Hirsch conjecturelinear programmingstrongly polynomial complexitytropical geometry

Mathematics Subject Classification ID

Foundations of tropical geometry and relations with algebra (14T10) Linear programming (90C05) Tropical optimization (e.g., max-plus optimization) (90C24) Interior-point methods (90C51)

Recommendations

• Complexity of solving tropical linear systems
• A note on tropical linear and integer programs
• Abstract tropical linear programming
• Complexity of tropical and MIN-plus linear prevarieties
• Tropicalizing the simplex algorithm
• Computing tropical linear spaces
• Polynomial Complexity Recognizing a Tropical Linear Variety
• Complexity of deciding whether a tropical linear prevariety is a tropical variety
• Tropical Convex Hull Computations
• On the frontiers of polynomial computations in tropical geometry

Cites work

• -convexity
• A Field of Generalised Puiseux Series for Tropical Geometry
• A friendly smoothed analysis of the simplex method
• A modified layered-step interior-point algorithm for linear programming
• A new polynomial-time algorithm for linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• A polynomial-time algorithm, based on Newton's method, for linear programming
• A primal-dual interior point method whose running time depends only on the constraint matrix
• A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
• A simple variant of the Mizuno-Todd-Ye predictor-corrector algorithm and its objective-function-free complexity
• A strongly polynomial algorithm for solving two-sided linear systems in max-algebra
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A Variant of the Vavasis--Ye Layered-Step Interior-Point Algorithm for Linear Programming
• Algebraic and Topological Tools in Linear Optimization
• An update on the Hirsch conjecture
• Asymptotic Linear Programming
• Central path curvature and iteration-complexity for redundant Klee-Minty cubes
• Combinatorial simplex algorithms can solve mean payoff games
• Duality and separation theorems in idempotent semimodules.
• Enumerative tropical algebraic geometry in ℝ²
• Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals
• Exponential behaviour of the Butkovič-Zimmermann algorithm for solving two-sided linear systems in max-algebra
• Handbook of Hilbert geometry
• scientific article; zbMATH DE number 4164543 (Why is no real title available?)
• scientific article; zbMATH DE number 479571 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 1944711 (Why is no real title available?)
• scientific article; zbMATH DE number 1503621 (Why is no real title available?)
• scientific article; zbMATH DE number 195007 (Why is no real title available?)
• scientific article; zbMATH DE number 6437647 (Why is no real title available?)
• scientific article; zbMATH DE number 964349 (Why is no real title available?)
• scientific article; zbMATH DE number 2221693 (Why is no real title available?)
• Information geometry and interior-point algorithms in semidefinite programs and symmetric cone programs
• Interior path following primal-dual algorithms. I: Linear programming
• Linear Programs and Convex Hulls Over Fields of Puiseux Fractions
• Log-Barrier Interior Point Methods Are Not Strongly Polynomial
• Logarithmic limit sets of real semi-algebraic sets
• Minimal half-spaces and external representation of tropical polyhedra
• Monomial Tropical Cones for Multicriteria Optimization
• NEWTON FLOW AND INTERIOR POINT METHODS IN LINEAR PROGRAMMING
• Non-archimedean amoebas and tropical varieties
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• On the complexity of following the central path of linear programs by linear extrapolation. II
• On the curvature of the central path of linear programming theory
• On the total curvature of tropical hypersurfaces
• Patchworking algebraic curves disproves the Ragsdale conjecture
• polymake: a framework for analyzing convex polytopes
• Polytopes and arrangements: diameter and curvature
• The central curve in linear programming
• The entropic barrier: exponential families, log-concave geometry, and self-concordance
• The Logarithmic Limit-Set of an Algebraic Variety
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• The real field with convergent generalized power series
• The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
• Tropical algebraic geometry
• Tropical convexity
• Tropical Polytopes and Cellular Resolutions
• Tropical spectrahedra
• Tropicalizing the simplex algorithm
• Who solved the Hirsch conjecture?

Cited in

(15)

• A tropical isoperimetric inequality
• Tropical Carathéodory with matroids
• The Gaussian entropy map in valued fields
• Tropicalizing the simplex algorithm
• The polyhedral geometry of truthful auctions
• Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria
• Asymmetric tropical distances and power diagrams
• The complexity of geometric scaling
• Higher rank inner products, Voronoi tilings and metric degenerations of tori
• Interior point methods in the year 2025
• Convex geometry over ordered hyperfields
• Interior point methods are not worse than simplex
• Signed tropicalization of polar cones
• The polyhedral geometry of truthful auctions
• Tropical lower bounds for extended formulations

Describes a project that uses

Uses Software

• polymake
• GitHub

This page was built for publication: What Tropical Geometry Tells Us about the Complexity of Linear Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5150211)