Laboratoire d'informatique de l'École polytechnique

GT Combi du Plateau de Saclay - mercredi 08/06 à 11h - Xavier Allamigeon

Speaker: Xavier Allamigeon (CMAP)
Location: Salle Philippe Flajolet, Bât. Alan Turing
Date: Mer. 8 juin. 2016, 11h00-12h00

Titre : Long and winding central paths

Résumé : 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 Ω(2r). 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.