Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method

DOI10.1137/070683386zbMath1200.68128arXivcs/0604055OpenAlexW2987042746WikidataQ123000106 ScholiaQ123000106MaRDI QIDQ3558017

R. V. Vershinin

Publication date: 29 April 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

simplex algorithmrandom polytopessmoothed analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55)

Related Items

Smoothed Analysis of Local Search Algorithms, Smoothed Analysis of the Successive Shortest Path Algorithm, Recent progress on the combinatorial diameter of polytopes and simplicial complexes, A Friendly Smoothed Analysis of the Simplex Method, On sub-determinants and the diameter of polyhedra, The isotropic constant of random polytopes with vertices on convex surfaces, On the shadow simplex method for curved polyhedra, Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit, The Effect of Adding Randomly Weighted Edges, Moser's shadow problem