What Tropical Geometry Tells Us about the Complexity of Linear Programming - Archive ouverte HAL Access content directly
Journal Articles SIAM Review Year : 2021

What Tropical Geometry Tells Us about the Complexity of Linear Programming

(1) , (2) , (1) , (3)
1
2
3
Xavier Allamigeon
Pascal Benchimol
  • Function : Author
Stéphane Gaubert

Abstract

Tropical geometry has been recently used to obtain new complexity results in convex optimization and game theory. In this paper, we present an application of this approach to a famous class of algorithms for linear programming, i.e., log-barrier interior point methods. We show that these methods are not strongly polynomial, by constructing a family of linear programs with 3r + 1 inequalities in dimension 2r for which the number of iterations performed is in Ω(2 r). The total curvature of the central path of these linear programs is also exponential in r, disproving a continuous analogue of the Hirsch conjecture proposed by Deza, Terlaky, and Zinchenko. These results are obtained by analyzing the tropical central path, which is the piecewise linear limit of the central paths of parameterized families of classical linear programs viewed through "logarithmic glasses." This allows us to provide combinatorial lower bounds for the number of iterations and the total curvature, in a general setting.
Fichier principal
Vignette du fichier
sigest-paper.pdf (671.94 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03505719 , version 1 (31-12-2021)

Identifiers

Cite

Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig. What Tropical Geometry Tells Us about the Complexity of Linear Programming. SIAM Review, 2021, 63 (1), pp.123-164. ⟨10.1137/20M1380211⟩. ⟨hal-03505719⟩
45 View
116 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More