Random walks on polytopes of constant corank

DOI10.4230/LIPICS.SOCG.2018.60MaRDI QIDQ5116520zbMATH OpenOpenAlexFDO

Authors Malte Milatz

Publication date 18 August 2020

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

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)

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.

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

Cites work

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

Cited in

(10)

• Random walks on the vertices of transportation polytopes with constant number of sources
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• RANDOM WALKS ON REGULAR POLYHEDRA AND OTHER DISTANCE–REGULAR GRAPHS
• scientific article; zbMATH DE number 2079356 (Why is no real title available?)
• One line and n points
• Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
• Directed random walks on polytopes with few facets
• Random walks on polytopes and an affine interior point method for linear programming
• Random walks in polytopes and negative dependence
• One line and \(n\) points

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)