Polytopes and Arrangements : Diameter and Curvature

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

Abstract: We introduce a continuous analogue of the Hirsch conjecture and a discrete analogue of the result of Dedieu, Malajovich and Shub. We prove a continuous analogue of the result of Holt and Klee, namely, we construct a family of polytopes which attain the conjectured order of the largest total curvature.

Keywords: polytopes, arrangements, diameter, central path

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Combinatorial Optimization (Polyhedra )

Citation: AdvOL-Report #2006/09 Advanced Optimization Laboratory, McMaster University, Hamilton, Ontario, Canada, August 2006.

Download: [Compressed Postscript][PDF]

Entry Submitted: 08/08/2006
Entry Accepted: 08/08/2006
Entry Last Modified: 09/27/2007

Modify/Update this entry