- Conference Paper
Rights / licenseCreative Commons Attribution 3.0 Unported
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. Show more
Toth, Csaba D.
Book title34th International Symposium on Computational Geometry (SoCG 2018)
Journal / seriesLeibniz International Proceedings in Informatics
Pages / Article No.
PublisherSchloss Dagstuhl, Leibniz-Zentrum für Informatik
Subjectpolytope; unique sink orientation; grid; random walk
Organisational unit03457 - Welzl, Emo / Welzl, Emo
MoreShow all metadata