Document Open Access Logo

On the Shadow Simplex Method for Curved Polyhedra

Authors Daniel Dadush, Nicolai Hähnle

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.345.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Author Details

Daniel Dadush
Nicolai Hähnle

Cite As Get BibTex

Daniel Dadush and Nicolai Hähnle. On the Shadow Simplex Method for Curved Polyhedra. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 345-359, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.345

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. (SOCG 2012), Brunsch and Röglin (ICALP 2013), and Eisenbrand and Vempala (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, 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((n^2 / delta) ln (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((n^3 / delta) ln (n / delta)) simplex pivots, each requiring O(mn) time to compute. An initial feasible solution can be found using O((mn^3 / delta) ln (n / delta)) pivot steps.

Subject Classification

Keywords
  • Optimization
  • Linear Programming
  • Simplex Method
  • Diameter of Polyhedra

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Karim Alexander Adiprasito and Bruno Benedetti. The Hirsch conjecture holds for normal flag complexes. Arxiv Report 1303.3598, 2014. Google Scholar
  2. M. L. Balinski. The Hirsch conjecture for dual transportation polyhedra. Math. Oper. Res., 9(4):629-633, 1984. Google Scholar
  3. David Barnette. An upper bound for the diameter of a polytope. Discrete Math., 10:9-13, 1974. Google Scholar
  4. Nicolas Bonifas, Marco Di Summa, Friedrich Eisenbrand, Nicolai Hähnle, and Martin Niemeier. On sub-determinants and the diameter of polyhedra. Discrete Comput. Geom., 52(1):102-115, 2014. Preliminary version in SOCG 12. Google Scholar
  5. Karl-Heinz Borgwardt. The simplex method: A probabilistic analysis, volume 1 of Algorithms and Combinatorics: Study and Research Texts. Springer-Verlag, Berlin, 1987. Google Scholar
  6. Graham Brightwell, Jan van den Heuvel, and Leen Stougie. A linear bound on the diameter of the transportation polytope. Combinatorica, 26(2):133-139, 2006. Google Scholar
  7. Tobias Brunsch and Heiko Röglin. Finding short paths on polytopes by the shadow vertex algorithm. In Automata, languages, and programming. Part I, volume 7965 of Lecture Notes in Comput. Sci., pages 279-290. Springer, Heidelberg, 2013. Google Scholar
  8. Daniel Dadush and Nicolas Bonifas. Short paths on the voronoi graph and closest vector problem with preprocessing. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 295-314. SIAM, 2015. Google Scholar
  9. Daniel Dadush and Nicolai Hähnle. On the shadow simplex method for curved polyhedra (draft of full paper). Arxiv Report 1412.6705, 2014. Google Scholar
  10. Jesús A. De Loera, Edward D. Kim, Shmuel Onn, and Francisco Santos. Graphs of transportation polytopes. J. Combin. Theory Ser. A, 116(8):1306-1325, 2009. Google Scholar
  11. Martin Dyer and Alan Frieze. Random walks, totally unimodular matrices, and a randomised dual simplex algorithm. Math. Programming, 64(1, Ser. A):1-16, 1994. Google Scholar
  12. Friedrich Eisenbrand and Santosh Vempala. Geometric random edge. Arxiv Report 1404.1568, 2014. Google Scholar
  13. Gil Kalai. The diameter of graphs of convex polytopes and f-vector theory. In Applied geometry and discrete mathematics, volume 4 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 387-411. Amer. Math. Soc., Providence, RI, 1991. Google Scholar
  14. Gil Kalai and Daniel J. Kleitman. A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull. Amer. Math. Soc. (N.S.), 26(2):315-316, 1992. Google Scholar
  15. D. G. Larman. Paths of polytopes. Proc. London Math. Soc. (3), 20:161-178, 1970. Google Scholar
  16. Benjamin Matschke, Francisco Santos, and Christophe Weibel. The width of 5-dimensional prismatoids. Arxiv Report 1202.4701, 2013. Google Scholar
  17. Denis Naddef. The Hirsch conjecture is true for (0,1)-polytopes. Math. Programming, 45(1, Ser. B):109-110, 1989. Google Scholar
  18. Francisco Santos. A counterexample to the Hirsch conjecture. Ann. of Math. (2), 176(1):383-412, 2012. Google Scholar
  19. Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385-463 (electronic), 2004. Google Scholar
  20. Michael J. Todd. An improved Kalai-Kleitman bound for the diameter of a polyhedron. Arxiv Report 1402.3579, 2014. Google Scholar
  21. Roman Vershynin. Beyond Hirsch conjecture: walks on random polytopes and smoothed complexity of the simplex method. SIAM J. Comput., 39(2):646-678, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact