Long and winding central paths

MaRDI QIDQ6251598zbMATH OpenFDO

Authors Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig

Publication date 16 May 2014

Mathematics Subject Classification ID

Interior-point methods (90C51)

Abstract: 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.

This page was built for publication: Long and winding central paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6251598)