Robust smoothed analysis of a condition number for linear programming

We perform a smoothed analysis of the GCC-condition number C(A) of the linear programming feasibility problem ∃x ∈ R ^m+1Ax <0. Suppose that A is any matrix with rows a of euclidean norm 1 and, independently for all i, let a _i be a random perturbation of aī following the uniform distribution in the spherical disk in S ^m of angular radius arcsin σ and centered at aī. We prove that E(lnC(A)) = O(mn/σ). A similar result was shown for Renegar's condition number and Gaussian perturbations by Dunagan et al. (Math Program Ser A, 2009). Our result is robust in the sense that it easily extends to radially symmetric probability distributions supported on a spherical disk of radius arcsin σ, whose density may even have a singularity at the center of the perturbation. Our proofs combine ideas from a recent paper of Bürgisser et al. (Math Comp 77(263), 2008) with techniques of Dunagan et al. © 2010 Springer and Mathematical Programming Society.