Random walks on polytopes of constant corank
OPEN ACCESS
Loading...
Author / Producer
Date
2018
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Book title
34th International Symposium on Computational Geometry (SoCG 2018)
Volume
99
Pages / Article No.
60
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
34th International Symposium on Computational Geometry (SoCG 2018)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
polytope; unique sink orientation; grid; random walk
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)