Random Walks on Polytopes of Constant Corank

DOI10.4230/LIPIcs.SoCG.2018.60zbMath1489.68367arXiv1802.09324OpenAlexW2964003114MaRDI QIDQ5116520

Malte Milatz

Publication date: 18 August 2020

Full work available at URL: https://arxiv.org/abs/1802.09324

zbMATH Keywords

polytoperandom walkgridunique sink orientation

Mathematics Subject Classification ID

Linear programming (90C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• A counterexample to the Hirsch conjecture
• The worst-case running time of the random simplex algorithm is exponential in the height
• Unique sink orientations of grids
• Completely unimodal numberings of a simple polytope
• Randomized simplex algorithms on Klee-Minty cubes
• Directed random walks on polytopes with few facets
• Random edge can be exponential on abstract cubes
• On the upper-bound conjecture for convex polytopes
• Grid orientations, \((d,d+2)\)-polytopes, and arrangements of pseudolines
• One line and n points
• The Simplex Algorithm in Dimension Three
• On the Monotone Upper Bound Problem
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

This page was built for publication: Random Walks on Polytopes of Constant Corank