2016
On the Shadow Simplex Method for curved polyhedra
Publication
Publication
Discrete & Computational Geometry p. 1- 28
We study the simplex method over polyhedra satisfying certain “discrete
curvature” lower bounds, which enforce that the boundary always meets vertices at
sharp angles. Motivated by linear programs with totally unimodular constraint matrices,
recent results of Bonifas et al. (Discrete Comput. Geom. 52(1):102–115, 2014),
Brunsch and Röglin (Automata, languages, and programming. Part I, pp. 279–290,
Springer, Heidelberg, 2013), and Eisenbrand and Vempala (http://arxiv.org/abs/1404.
1568, 2014) have improved our understanding of such polyhedra. We develop a new
type of dual analysis of the shadow simplex method which provides a clean and powerful
tool for improving all previously mentioned results. Our methods are inspired
by the recent work of Bonifas and the first named author (in: Indyk P (ed) Proceedings
of the Twenty-Sixth Annual ACM–SIAM Symposium on Discrete Algorithms,
pp. 295–314, SIAM, 2015), who analyzed a remarkably similar process as part of
an algorithm for the Closest Vector Problem with Preprocessing. For our first result,
we obtain a constructive diameter bound of O( n2
δ ln n
δ ) for n-dimensional polyhedra
with curvature parameter δ ∈ (0, 1]. For the class of polyhedra arising from totally
unimodular constraint matrices, this implies a bound of O(n3 ln n). For linear optimization,
given an initial feasible vertex, we show that an optimal vertex can be found
using an expected O( n3
δ ln n
δ ) simplex pivots, each requiring O(mn) time to compute,
where m is the number of constraints. An initial feasible solution can be found using
O(mn3
δ ln n
δ ) pivot steps
Additional Metadata | |
---|---|
, , , | |
springer | |
Discrete & Computational Geometry | |
Organisation | Networks and Optimization |
Dadush, D., & Hähnle, N. (2016). On the Shadow Simplex Method for curved polyhedra. Discrete & Computational Geometry, 1–28. |