Long and winding central paths

Xavier Allamigeon 1, 2 Pascal Benchimol 1, 2 Stéphane Gaubert 2, 1 Michael Joswig 3
2 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR
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

https://hal.inria.fr/hal-01096452
Contributeur : Xavier Allamigeon <>
Soumis le : mercredi 17 décembre 2014 - 15:16:01
Dernière modification le : jeudi 11 janvier 2018 - 06:22:34

Identifiants

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

Collections

Citation

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

Partager

Métriques

Consultations de la notice

267