What Tropical Geometry Tells Us about the Complexity of Linear Programming - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue SIAM Review Année : 2021

What Tropical Geometry Tells Us about the Complexity of Linear Programming

Xavier Allamigeon
Pascal Benchimol
  • Fonction : Auteur
Stéphane Gaubert

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

Citer

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⟩
83 Consultations
347 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More