Random walks on polytopes of constant corank

DOI10.4230/LIPICS.SOCG.2018.60zbMATH Open1489.68367arXiv1802.09324OpenAlexW2964003114MaRDI QIDQ5116520FDOQ5116520

Malte Milatz

Publication date: 18 August 2020

Abstract: We show that the pivoting process associated with one line and $n$ points in $r$-dimensional space may need $Omega(lo{g}^{r}n)$ steps in expectation as $noinfty$. The only cases for which the bound was known previously were for $rle3$. 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.

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

Recommendations

• One line and \(n\) points
• One line and n points
• Two New Bounds for the Random‐Edge Simplex‐Algorithm
• The Random‐Facet simplex algorithm on combinatorial cubes
• Directed random walks on polytopes with few facets

zbMATH Keywords

gridrandom walkpolytopeunique sink orientation

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• The Simplex Algorithm in Dimension Three
• On the Monotone Upper Bound Problem
• Unique sink orientations of grids
• A counterexample to the Hirsch conjecture
• Randomized simplex algorithms on Klee-Minty cubes
• The worst-case running time of the random simplex algorithm is exponential in the height
• Completely unimodal numberings of a simple polytope
• 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
• Directed random walks on polytopes with few facets

Cited In (6)

• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• RANDOM WALKS ON REGULAR POLYHEDRA AND OTHER DISTANCE–REGULAR GRAPHS
• Title not available (Why is that?)
• One line and n points
• Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
• Random walks on the vertices of transportation polytopes with constant number of sources

This page was built for publication: Random walks on polytopes of constant corank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116520)