@article{BA-Robust-Smoothed-Analysis-Of-A-Condition-Number-For-Linear-Programming,
Title = {Robust Smoothed Analysis of a Condition Number for Linear Programming},
Author = {Peter Bürgisser and Dennis Amelunxen},
Pages = {221-251},
Year = {2012},
Issn = {0025-5610},
Doi = {10.1007/s10107-010-0346-x},
Journal = {Mathematical Programming},
Volume = {131},
Number = {1-2, Ser. A},
Abstract = {We perform a smoothed analysis of the GCC-condition number $C(A)$ of the linear programming feasibility problem $\exists x\in\mathbb R^{m+1} Ax < 0$. Suppose that $\bar{A}$ is any matrix with rows $\bar{a_i}$ of euclidean norm $1$ and, independently for all $i$, let $a_i$ be a random perturbation of $\bar{a_i}$ following the uniform distribution in the spherical disk in $S^m$ of angular radius $\arcsin\sigma$ and centered at $\bar{a_i}$. We prove that $E(\ln C(A)) = O(mn / \sigma)$. A similar result was shown for Renegar's condition number and Gaussian perturbations by Dunagan, Spielman, and Teng [arXiv:cs.DS/0302011]. Our result is robust in the sense that it easily extends to radially symmetric probability distributions supported on a spherical disk of radius $\arcsin\sigma$, whose density may even have a singularity at the center of the perturbation. Our proofs combine ideas from a recent paper of Bürgisser, Cucker, and Lotz (Math. Comp. 77, No. 263, 2008) with techniques of Dunagan et al.},
Url = {http://arxiv.org/abs/0803.0925},
Url2 = {http://www3.math.tu-berlin.de/algebra/work/arxiv0803.0925v3.pdf}
}