Smoothed analysis of condition numbers and complexity implications for linear programming |
| |
| Authors: | John Dunagan Daniel A. Spielman Shang-Hua Teng |
| |
| Affiliation: | (1) Department of Mathematics, Second University of Naples, via Vivaldi, 43, I-81100 Caserta, Italy |
| |
| Abstract: | ![]()
We perform a smoothed analysis of Renegar’s condition number for linear programming by analyzing the distribution of the distance to ill-posedness of a linear program subject to a slight Gaussian perturbation. In particular, we show that for every n-by-d matrix Ā, n-vector [`(varvec b)]{bar{varvec b}}, and d-vector [`(varvec c)]{bar{varvec c}} satisfying ||[`(A)], [`(varvec b)], [`(varvec c)]||F ￡ 1{{||bar{bf A}, bar{varvec b}, bar{varvec c}||_F leq 1}} and every σ ≤ 1, | EA,varvec b,varvec c [logC (A,varvec b,varvec c) = O (log(nd/s)),mathop{bf E}limits_{bf A,varvec b,varvec c }{{[log C (bf A,varvec b,varvec c)} = O (log (nd/sigma)),} |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
|
