Abstract
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(\frac{n^2}{\delta } \ln \frac{n}{\delta })\) for n-dimensional polyhedra with curvature parameter \(\delta \in (0,1]\). For the class of polyhedra arising from totally unimodular constraint matrices, this implies a bound of \(O(n^3 \ln n)\). For linear optimization, given an initial feasible vertex, we show that an optimal vertex can be found using an expected \(O(\frac{n^3}{\delta } \ln \frac{n}{\delta })\) 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(\frac{m n^3}{\delta } \ln \frac{n}{\delta })\) pivot steps.
Similar content being viewed by others
Notes
We note that this measure is already implicit in [4] and that the diameter bound factors through it.
However, the \(\tau \)-wide property is weaker even when all normal cones are simplicial: a 2-dimensional cone of inner angle close to \(\pi \) is almost 1-wide, but satisfies \(\delta \)-distance only for \(\delta \) close to 0.
The \(\delta \)-distance property is invariant under scaling, so the choice of generators of the extreme rays is irrelevant.
In the final bound, the loss of a factor n here disappears inside a logarithm.
Alternatively, one can apply a rotation and translation so that \(F_i\) lies in the subspace \(\mathbb {R}^{n-1}\) spanned by the first \(n-1\) coordinates. The rotation does not affect the \(\delta \)-distance property, and we can then treat \(F_i\) as a polytope in \(\mathbb {R}^{n-1}\).
This is just a different way of saying that \((\mathbf {c}_{\lambda ^\star })_{i^\star } = 0\). Due to the precondition on \([\mathbf {c},\mathbf {d})\) this index is uniquely defined when \(\lambda ^\star < 1\).
Note that the minimum is positive and unique because the underlying polyhedron is simple.
References
Adiprasito, K.A., Benedetti, B.: The Hirsch conjecture holds for normal flag complexes. Math. Oper. Res. 39(4), 1340–1348 (2014)
Balinski, M.L.: The Hirsch conjecture for dual transportation polyhedra. Math. Oper. Res. 9(4), 629–633 (1984)
Barnette, David: An upper bound for the diameter of a polytope. Discrete Math. 10, 9–13 (1974)
Bonifas, N., Di Summa, M., Eisenbrand, F., Hähnle, N., Niemeier, M.: On sub-determinants and the diameter of polyhedra. Discrete Comput. Geom. 52(1), 102–115 (2014). Preliminary version in SOCG 12
Borgwardt, K.-H.: The Simplex Method: A Probabilistic Analysis. Algorithms and Combinatorics: Study and Research Texts. Springer, Berlin (1987)
Brightwell, G., van den Heuvel, J., Stougie, J.: A linear bound on the diameter of the transportation polytope. Combinatorica 26(2), 133–139 (2006)
Brunsch, T., Röglin, H.: Finding short paths on polytopes by the shadow vertex algorithm. Automata, Languages, And Programming, Part I. Lecture Notes in Computer Science, pp. 279–290. Springer, Heidelberg (2013)
Dadush, D., Bonifas, N.: Short paths on the Voronoi graph and closest vector problem with preprocessing. In: Indyk, P. (eds) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, 4–6 Jan 2015, pp. 295–314. SIAM, 2015
De Loera, J.A., Kim, E.D., Onn, S., Santos, F.: Graphs of transportation polytopes. J. Combin. Theory Ser. A 116(8), 1306–1325 (2009)
Dyer, M., Frieze, A.: Random walks, totally unimodular matrices, and a randomised dual simplex algorithm. Math. Program. 64(1, Ser. A), 1–16 (1994)
Eisenbrand, F., Vempala, S.: Geometric random edge. arXiv:1404.1568 (2014)
Kalai, G.: The diameter of graphs of convex polytopes and \(f\)-vector theory. Applied Geometry and Discrete Mathematics. DIMACS Series Discrete Mathematics and Theoretical Computer Science, pp. 387–411. American Mathematical Society, Providence, RI (1991)
Kalai, G., Kleitman, D.J.: A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull. Am. Math. Soc. (N.S.) 26(2), 315–316 (1992)
Larman, D.G.: Paths of polytopes. Proc. Lond. Math. Soc. 3(20), 161–178 (1970)
Matschke, B., Santos, F., Weibel, C.: The width of 5-dimensional prismatoids. arXiv:1202.4701 (2013)
Naddef, D.: The Hirsch conjecture is true for (0,1)-polytopes. Math. Program. 45(1, Ser. B), 109–110 (1989)
Santos, F.: A counterexample to the Hirsch conjecture. Ann. Math. 176(1), 383–412 (2012)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003)
Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385–463 (2004)
Todd, M.J.: An improved Kalai-Kleitman bound for the diameter of a polyhedron. SIAM J. Discrete Math. 28(4), 1944–1947 (2014)
Vershynin, R.: Beyond Hirsch conjecture: walks on random polytopes and smoothed complexity of the simplex method. SIAM J. Comput. 39(2), 646–678 (2009)
Acknowledgments
We would like to thank Friedrich Eisenbrand and Santosh Vempala for useful discussions. We also thank the anonymous reviewers for their useful comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editor in Charge: János Pach
Rights and permissions
About this article
Cite this article
Dadush, D., Hähnle, N. On the Shadow Simplex Method for Curved Polyhedra. Discrete Comput Geom 56, 882–909 (2016). https://doi.org/10.1007/s00454-016-9793-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-016-9793-3