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
http://arxiv.org/abs/cs.DS/0302011.
Abstract
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