Discrete Mathematics and Optimization Seminar

---

ANTOINE DEZA
McMasters University
Monday November 19th at 4.30pm
Burnside 1205



Title. Intriguing analogies between the edge and central paths

Abstract. Linear optimization consists of maximizing, or minimizing, a linear function over
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.