Long and winding central paths

Abstract : We disprove a continuous analog of the Hirsch conjecture proposed by Deza, Terlaky and Zinchenko, by constructing a family of linear programs with 3r+4 inequalities in dimension 2r+2 where the central path has a total curvature in Ω(2r/r). Our method is to tropicalize the central path in linear programming. The tropical central path is the piecewise-linear limit of the central paths of parameterized families of classical linear programs viewed through logarithmic glasses. We show in particular that the tropical analogue of the analytic center is nothing but the tropical barycenter, i.e., the maximum of a tropical polyhedron. It follows that unlike in the classical case, the tropical central path may lie on the boundary of the tropicalization of the feasible set, and may even coincide with a path of the tropical simplex method. Finally, our counter-example is obtained as a deformation of a family of tropical linear programs introduced by Bezem, Nieuwenhuis and Rodríguez-Carbonell.
Type de document :
Pré-publication, Document de travail
Preprint arXiv:1405.4161. 2014
Liste complète des métadonnées

Contributeur : Xavier Allamigeon <>
Soumis le : mercredi 17 décembre 2014 - 15:16:01
Dernière modification le : mercredi 14 novembre 2018 - 15:20:11

Lien texte intégral


  • HAL Id : hal-01096452, version 1
  • ARXIV : 1405.4161



Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig. Long and winding central paths. Preprint arXiv:1405.4161. 2014. 〈hal-01096452〉



Consultations de la notice