Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
From MaRDI portal
Publication:3558017
DOI10.1137/070683386zbMath1200.68128arXivcs/0604055WikidataQ123000106 ScholiaQ123000106MaRDI QIDQ3558017
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
68Q25: Analysis of algorithms and problem complexity
52B55: Computational aspects related to convexity
Related Items
The Effect of Adding Randomly Weighted Edges, A Friendly Smoothed Analysis of the Simplex Method, On sub-determinants and the diameter of polyhedra, Recent progress on the combinatorial diameter of polytopes and simplicial complexes, On the shadow simplex method for curved polyhedra, Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit, The isotropic constant of random polytopes with vertices on convex surfaces, Moser's shadow problem, Smoothed Analysis of Local Search Algorithms, Smoothed Analysis of the Successive Shortest Path Algorithm