講演者： Antoine Deza 氏 （McMaster University）
タイトル： Polytopes and Arrangements: Diameter and Curvature
概要：Linear optimization consists of maximizing, or minimizing, a linear
function over a domain defined by a set of linear inequalities. The
simplex and primal-dual interior point methods are currently the most
computationally successful algorithms. In this talk we highlight
intriguing links between the edge-path followed by the simplex and the
central path followed by interior point methods. By analogy with the
conjecture of Hirsch, we conjecture that the order of the largest total
curvature of the central path associated to a polytope is the number of
inequalities defining the polytope. By analogy with a result of Dedieu,
Malajovich and Shub, we conjecture that the average diameter of a
bounded cell of an arrangement is less than the dimension. 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 total curvature, and we prove that the special case where
the number of inequalities is twice the dimension is equivalent to the
general case. We substantiate these conjectures in low dimensions and
highlight additional links.
This talk is based on a joint work with Tamas Terlaky
and Yuriy Zinchenko
