Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal.inria.fr/hal-01096452
Contributor : Xavier Allamigeon <>
Submitted on : Wednesday, December 17, 2014 - 3:16:01 PM
Last modification on : Thursday, March 5, 2020 - 6:34:12 PM

Links full text

Identifiers

  • 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. 2014. ⟨hal-01096452⟩

Share

Metrics

Record views

373