46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) Improved Smoothed Analysis of the Shadow Vertex Simplex Method Pittsburgh, Pennsylvania, USA October 23-October 25 ISBN: 0-7695-2468-0
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.44
Spielman and Teng (JACM ?04), proved that the smoothed complexity of a two-phase shadow-vertex method for linear programming is polynomial in the number of constraints n, the number of variables d, and the parameter of perturbation 1/\sigma. The key geometric result in their proof was an upper bound of o(nd^3 /\min (\sigma ,(9d\ln n)^{ - 1/2} )^6 ) on the expected size of the shadow of the polytope de?ned by the perturbed linear program. In this paper, we give a much simpler proof of a better bound: o(n^3 d\ln n/\min (\sigma ,(4d\ln n)^{ - 1/2} )^2 ) When evaluated at \sigma = (9d\ln n)^{ - 1/2}, this improves the size estimate from O(nd^6 \ln ^3 n) to o(n^2 d^2 \ln n). The improvement only becomes better as s decreases.
Citation:
Amit Deshpande, Daniel A. Spielman, "Improved Smoothed Analysis of the Shadow Vertex Simplex Method," focs, pp.349-356, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||