The continuous d-step conjecture for polytopes

Antoine Deza(dezamcmaster.ca)
Tamas Terlaky(terlakymcmaster.ca)
Yuriy Zinchenko(zinchenmcmaster.ca)

Abstract: The curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. We prove the analogue of the result of Klee and Walkup. Namely, we show that if the order of the curvature is less than the dimension $d$ for all polytope defined by 2d inequalities and for all d, then the order of the curvature is less that the number of inequalities for all polytopes.

Keywords: polytopes, diameter, Hirsch conjecture, d-step conjecture, central path, curvature

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Combinatorial Optimization (Polyhedra )

Citation: AdvOL-Report #2007/16 Advanced Optimization Laboratory, McMaster University, Hamilton, Ontario, Canada, September 2007.

Download: [PDF]

Entry Submitted: 09/28/2007
Entry Accepted: 09/28/2007
Entry Last Modified: 09/28/2007

Modify/Update this entry