
Open access
Author
Date
2018Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
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. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000273186Publication status
publishedExternal links
Book title
34th International Symposium on Computational Geometry (SoCG 2018)Journal / series
Leibniz International Proceedings in Informatics (LIPIcs)Volume
Pages / Article No.
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für InformatikEvent
Subject
polytope; unique sink orientation; grid; random walkOrganisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
More
Show all metadata
ETH Bibliography
yes
Altmetrics