Long and Winding Central Paths

Xavier Allamigeon 1, 2 Pascal Benchimol 1, 2 Stephane Gaubert 1, 2 Michael Joswig 3
1 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
2 CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique
3 Darmstadt University of Technology [Darmstadt]
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 Ω(2^r/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 linear programs viewed through logarithmic glasses.
Type de document :
Communication dans un congrès
SIAM Conference on Control and its Applications (SIAM CT’15), Jul 2015, Paris, France. 〈http://www.siam.org/meetings/ct15/index.php〉
Liste complète des métadonnées
https://hal.inria.fr/hal-01263337
Contributeur : Marianne Akian <>
Soumis le : mercredi 27 janvier 2016 - 16:31:37
Dernière modification le : mercredi 14 novembre 2018 - 15:20:12

Identifiants

  • HAL Id : hal-01263337, version 1

Collections

X | INSMI | X-CMAP | CMAP | INRIA | PARISTECH | TDS-MACS | UNIV-PARIS-SACLAY | X-DEP-MATHA

Citation

Xavier Allamigeon, Pascal Benchimol, Stephane Gaubert, Michael Joswig. Long and Winding Central Paths. SIAM Conference on Control and its Applications (SIAM CT’15), Jul 2015, Paris, France. 〈http://www.siam.org/meetings/ct15/index.php〉. 〈hal-01263337〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

330

Contact


archive-ouverte@inria.fr