Home > Department of Mathematics > Seminars > OR Seminar Series > Academic year 2014-15 > New Bounds for Curved Polyhedra via the Shadow Simplex Method
How to contact us


LSE 10 logo master_6

Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE


Enquiries: dom.events@lse.ac.uk 


Follow us online



New Bounds for Curved Polyhedra via the Shadow Simplex Method

Wednesday 3 December 2014
Daniel Dadush
3pm - 4pm, 32L.G.20


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).

Daniel Dadush