What Tropical Geometry Tells Us about the Complexity of Linear Programming

DOI10.1137/20M1380211zbMath1459.90124MaRDI QIDQ5150211

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

Publication date: 10 February 2021

Published in: SIAM Review (Search for Journal in Brave)

zbMATH Keywords

linear programming; central path; tropical geometry; strongly polynomial complexity; continuous analogue of the Hirsch conjecture

Mathematics Subject Classification ID

90C05: Linear programming

90C51: Interior-point methods

14T10: Foundations of tropical geometry and relations with algebra

90C24: Tropical optimization (e.g., max-plus optimization)

Uses Software

• polymake
• GitHub