This is an announcement for the paper "Beyond Hirsch Conjecture: walks on random polytopes and smoothed complexity of the simplex method" by Roman Vershynin.
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 had polynomial smoothed complexity. On a slight random perturbation of 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(min(d^5 log^2(n), d^9 log^4(d), d^3 sigma^{-4})). This shows that the tight Hirsch conjecture n-d on the 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. 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. So, in expectation it takes a constant number of independent trials until a correct solution is found. 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.
Archive classification: Data Structures and Algorithms; Functional Analysis
Remarks: 17 pages
The source file(s), , is(are) stored in gzipped form as with size . The corresponding postcript file has gzipped size .
Submitted from: vershynin@math.ucdavis.edu
The paper may be downloaded from the archive by web browser from URL
http://front.math.ucdavis.edu/cs.DS/0604055
or
http://arXiv.org/abs/cs.DS/0604055
or by email in unzipped form by transmitting an empty message with subject line
uget 04055
or in gzipped form by using subject line
get 04055
to: math@arXiv.org.