Wednesday 3 December 2014
Daniel Dadush
3pm - 4pm, 32L.G.20
Abstract
We study the simplex method over polyhedra satisfying certain "discrete curvature" lower bounds. Intuitively speaking, for the polyhedra in question, we enforce that the boundary always meets vertices at ``sharp'' angles.
Our work builds and improves upon the results of Bonifas et al (SOCG 2012), Brunsch and Roglin (ICALP 2013), and Eisenbrand, Vempala (2014). As our main results, we give an improved (constructive) diameter bound over these polytopes, as well as a faster simplex based algorithm for linear optimization. As our main technical tool, we develop a new analysis and variant of the shadow simplex method.
More precisely, for an n-dimensional polyhedron with m facets and curvature parameter 0 < delta < 1, we give a diameter bound of O(n^2(1+ ln(n/delta))/delta). For the class of polyhedra having totally unimodular constraint matrices, this implies an O(n^3 ln n) diameter bound. For linear optimization, given an initial feasible vertex, we show that an optimal vertex can be found using an expected O(n^3(1+ln(n/delta))/delta) simplex pivots, each requiring O(m n) time to compute. Furthermore, a first feasible solution can be found using O(m n^3(1+ln(n/delta))/delta) pivot steps.
This is joint work with Nicolai Hahnle (University of Bonn).