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.