Long and winding central paths

2014/05/16 by Xavier Allamigeon, Allamigeon, Xavier, Pascal Benchimol +5
Computer Science · Mathematics · #14T05 #90C51 #Advanced Graph Theory Research #Combinatorics (math.CO) #Commutative Algebra and Its Applications #Computational Geometry and Mesh Generation #FOS: Mathematics #Optimization and Control (math.OC) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.1405.4161

openalex publication_date 2014/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 Ω(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.

Related

• On the Curvature of the Central Path of Linear Programming Theory
• The tropicalization of the entropic barrier
• The degree of the central curve in semidefinite, linear, and quadratic programming
• Geometry in the tropical limit
• Tropical linear systems and the realizability problem