Smoothed Analysis of Renegar's Condition Number for Linear Programming

Authors: John D. Dunagan, Daniel A. Spielman, and Shang-Hua Teng .

Bibliographic Information: Available at


For any linear program, we show that a slight random relative perturbation of that linear program has small condition number with high probability. Following Spielman-Teng, we call this smoothed analysis of the condition number. Part of our main result is that the expectation of the log of the condition number of any appropriately scaled linear program subject to a Gaussian perturbation of variance $\sigma^2$ is at most $O(\log nd/\sigma)$ with high probability. Since the condition number bounds the running time of many algorithms for convex programming, this may explain their observed fast convergence.
You can download this paper as Postscript, or PDF.
Daniel A. Spielman
Last modified: Wed Oct 13 23:36:44 EDT 2004