Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
From MaRDI portal
Publication:3558017
DOI10.1137/070683386zbMATH Open1200.68128arXivcs/0604055OpenAlexW2987042746WikidataQ123000106 ScholiaQ123000106MaRDI QIDQ3558017FDOQ3558017
Authors: Roman Vershynin 
Publication date: 29 April 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Abstract: The smoothed analysis of algorithms is concerned with the expected running time of an algorithm under slight random perturbations of arbitrary inputs. Spielman and Teng proved that the shadow-vertex simplex method has polynomial smoothed complexity. On a slight random perturbation of an arbitrary linear program, the simplex method finds the solution after a walk on polytope(s) with expected length polynomial in the number of constraints n, the number of variables d and the inverse standard deviation of the perturbation 1/sigma. We show that the length of walk in the simplex method is actually polylogarithmic in the number of constraints n. Spielman-Teng's bound on the walk was O(n^{86} d^{55} sigma^{-30}), up to logarithmic factors. We improve this to O(log^7 n (d^9 + d^3 s^{-4})). This shows that the tight Hirsch conjecture n-d on the length of walk on polytopes is not a limitation for the smoothed Linear Programming. Random perturbations create short paths between vertices. We propose a randomized phase-I for solving arbitrary linear programs, which is of independent interest. Instead of finding a vertex of a feasible set, we add a vertex at random to the feasible set. This does not affect the solution of the linear program with constant probability. This overcomes one of the major difficulties of smoothed analysis of the simplex method -- one can now statistically decouple the walk from the smoothed linear program. This yields a much better reduction of the smoothed complexity to a geometric quantity -- the size of planar sections of random polytopes. We also improve upon the known estimates for that size, showing that it is polylogarithmic in the number of vertices.
Full work available at URL: https://arxiv.org/abs/cs/0604055
Recommendations
- Random walks on polytopes and an affine interior point method for linear programming
- Random walks on polytopes and an affine interior point method for linear programming
- scientific article; zbMATH DE number 4119095
- Convex hulls of random walks, hyperplane arrangements, and Weyl chambers
- RANDOM WALKS ON REGULAR POLYHEDRA AND OTHER DISTANCE–REGULAR GRAPHS
- Random walks on simplicial complexes and the normalized Hodge 1-Laplacian
- Directed random walks on polytopes with few facets
- Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
- Random walks on polytopes of constant corank
Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55)
Cited In (14)
- Moser's shadow problem
- Circuits in extended formulations
- A friendly smoothed analysis of the simplex method
- Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
- A friendly smoothed analysis of the simplex method
- On sub-determinants and the diameter of polyhedra
- On the shadow simplex method for curved polyhedra
- Recent progress on the combinatorial diameter of polytopes and simplicial complexes
- A spectral approach to polytope diameter
- The effect of adding randomly weighted edges
- Smoothed analysis of the successive shortest path algorithm
- Upper and lower bounds on the smoothed complexity of the simplex method
- The isotropic constant of random polytopes with vertices on convex surfaces
- Smoothed analysis of local search algorithms
This page was built for publication: Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3558017)
