%0 Journal Article
%T Long and winding central paths
%A Xavier Allamigeon
%A Pascal Benchimol
%A St¨¦phane Gaubert
%A Michael Joswig
%J Mathematics
%D 2014
%I arXiv
%X We disprove a continuous analogue 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 $\Omega(2^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. The lower bound for the classical curvature is obtained by developing a combinatorial concept of a tropical angle.
%U http://arxiv.org/abs/1405.4161v2