TU Berlin

Fachgebiet Algorithmische AlgebraJournal Publications

Inhalt des Dokuments

zur Navigation

Journal Publications

Robust Smoothed Analysis of a Condition Number for Linear Programming
Zitatschlüssel BA-Robust-Smoothed-Analysis-Of-A-Condition-Number-For-Linear-Programming
Autor Peter Bürgisser and Dennis Amelunxen
Seiten 221-251
Jahr 2012
ISSN 0025-5610
DOI 10.1007/s10107-010-0346-x
Journal Mathematical Programming
Jahrgang 131
Nummer 1-2, Ser. A
Zusammenfassung 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 $\barA$ is any matrix with rows $\bara_i$ of euclidean norm $1$ and, independently for all $i$, let $a_i$ be a random perturbation of $\bara_i$ following the uniform distribution in the spherical disk in $S^m$ of angular radius $\arcsin\sigma$ and centered at $\bara_i$. We prove that $E(łn 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.
Link zur Publikation Link zur Originalpublikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe