Monday November 19th at 4.30pm

a domain defined by a set of linear inequalities. The simplex methods, which follow an edge-path,

and the primal-dual interior point methods, which follow the central path, are currently

the most computationally successful algorithms. In this talk we highlight intriguing

analogies between the edge and central paths, and between the diameter of a polytope and the

largest possible total curvature of the associated central path.

We show that the addition of an exponential number of redundant inequalities may force

the central path to visit all the vertices of the Klee-Minty cube in the same order as

simplex methods do. We prove continuous analogues of two results of Holt-Klee and Klee-Walkup:

We construct a family of polytopes which attain the conjectured order of the largest

curvature, and prove that the special case where the number of inequalities is twice the dimension is

equivalent to the general case. We show that the conjectured bound for the average

diameter of a bounded cell of a simple hyperplane arrangement is asymptotically tight for fixed

dimension.

Links with the conjecture of Hirsch, Haimovich's probabilistic analysis of the

shadow-vertex simplex algorithm, and the result of Dedieu, Malajovich and Shub on the average total

curvature of a bounded cell are also presented.

This talk is based on recent joint-works with Tamas Terlaky, Yuriy Zinchenko and Feng Xie.