Inhalt des Dokuments
Dr. Dennis Amelunxen
KontaktCity University of Hong Kong
Department of Mathematics
G6613 (Green Zone), 6/F Academic 1
Tat Chee Avenue, Kowloon Tong, Hong Kong Persönliche Homepage
sites.google.com/site/dennisamelunxen/home
Publikationen in der Arbeitsgruppe
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. |
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe
Hilfsfunktionen
Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.