Document Open Access Logo

Random Walks on Polytopes of Constant Corank

Author Malte Milatz

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.60.pdf
  • Filesize: 0.6 MB
  • 14 pages

Document Identifiers

Author Details

Malte Milatz

Cite As Get BibTex

Malte Milatz. Random Walks on Polytopes of Constant Corank. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.60

Abstract

We show that the pivoting process associated with one line and n points in r-dimensional space may need Omega(log^r n) steps in expectation as n -> infty. The only cases for which the bound was known previously were for r <= 3. Our lower bound is also valid for the expected number of pivoting steps in the following applications: (1) The Random-Edge simplex algorithm on linear programs with n constraints in d = n-r variables; and (2) the directed random walk on a grid polytope of corank r with n facets.

Subject Classification

Keywords
  • polytope
  • unique sink orientation
  • grid
  • random walk

Metrics

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

References

  1. Andrei Z. Broder, Martin E. Dyer, Alan M. Frieze, Prabhakar Raghavan, and Eli Upfal. The worst-case running time of the random simplex algorithm is exponential in the height. Inf. Process. Lett., 56(2):79-81, 1995. Google Scholar
  2. Stefan Felsner, Bernd Gärtner, and Falk Tschirschnitz. Grid orientations, (d,d+2)-polytopes, and arrangements of pseudolines. Discrete & Computational Geometry, 34(3):411-437, 2005. Google Scholar
  3. Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick. Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pages 283-292, 2011. Google Scholar
  4. Bernd Gärtner, Martin Henk, and Günter M. Ziegler. Randomized simplex algorithms on klee-minty cubes. Combinatorica, 18(3):349-372, 1998. Google Scholar
  5. Bernd Gärtner, Walter D. Morris, Jr., and Leo Rüst. Unique sink orientations of grids. Algorithmica, 51:200-235, 2008. Google Scholar
  6. Bernd Gärtner, József Solymosi, Falk Tschirschnitz, Pavel Valtr, and Emo Welzl. One line and n points. Random Structures &Algorithms, 23(4):453-471, 2003 (preliminary version at STOC 2001). Google Scholar
  7. Branko Grünbaum. Convex polytopes. Springer, New York, 1967/2003. Google Scholar
  8. Kathy Williamson Hoke. Completely unimodal numberings of a simple polytope. Discrete Applied Mathematics, 20(1):69-81, 1988. Google Scholar
  9. Volker Kaibel, Rafael Mechtel, Micha Sharir, and Günter M. Ziegler. The simplex algorithm in dimension three. SIAM Journal on Computing, 34(2):475-497, 2005. Google Scholar
  10. Gil Kalai. A subexponential randomized simplex algorithm. In Proc. 24th ACM Symposium on Theory of Computing, pages 475-482, 1992. Google Scholar
  11. Jiří Matoušek and Tibor Szabó. Random edge can be exponential on abstract cubes. Advances in Mathematics, 204(1):262-277, 2006. Google Scholar
  12. Peter McMullen. On the upper-bound conjecture for convex polytopes. Journal of Combinatorial Theory, Series B, 10(3):187-200, 1971. Google Scholar
  13. Malte Milatz. Directed random walks on polytopes with few facets. Electronic Notes in Discrete Mathematics, 61:869-875, 2017. The European Conference on Combinatorics, Graph Theory and Applications (Eurocomb '17). Google Scholar
  14. Julian Pfeifle and Günter M. Ziegler. On the monotone upper bound problem. Experimental Mathematics, 13(1):1-12, 2004. Google Scholar
  15. Francisco Santos. A counterexample to the Hirsch Conjecture. Annals of Mathematics, 176:383-412, 2012. Google Scholar
  16. Falk Tschirschnitz. LP-related properties of polytopes with few facets. PhD thesis, ETH Zürich, 2003. 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