@ARTICLE{BA-Robust-Smoothed-Analysis-Of-A-Condition-Number-For-Linear-Programming,
 ISSN={0025-5610},
 JOURNAL={Mathematical Programming},
 TITLE={Robust Smoothed Analysis of a Condition Number for Linear Programming},
 VOLUME={131},
 AUTHOR={Peter Bürgisser and Dennis Amelunxen},
 YEAR={2012},
 URL={http://arxiv.org/abs/0803.0925},
 PAGES={221-251},
 DOI={10.1007/s10107-010-0346-x},
 URL2={http://dx.doi.org/10.1007/s10107-010-0346-x},
 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.},
 NUMBER={1-2, Ser. A}
}

{"_id":"TZGt2fEeCCoBmpTTM","bibbaseid":"brgisser-amelunxen-robustsmoothedanalysisofaconditionnumberforlinearprogramming-2012","downloads":0,"creationDate":"2017-01-04T12:11:10.567Z","title":"Robust Smoothed Analysis of a Condition Number for Linear Programming","author_short":["Bürgisser, P.","Amelunxen, D."],"year":2012,"bibtype":"article","biburl":"http://www3.math.tu-berlin.de/algebra/static/papers.parsed.bib","bibdata":{"bibtype":"article","type":"article","issn":"0025-5610","journal":"Mathematical Programming","title":"Robust Smoothed Analysis of a Condition Number for Linear Programming","volume":"131","author":[{"firstnames":["Peter"],"propositions":[],"lastnames":["Bürgisser"],"suffixes":[]},{"firstnames":["Dennis"],"propositions":[],"lastnames":["Amelunxen"],"suffixes":[]}],"year":"2012","url":"http://arxiv.org/abs/0803.0925","pages":"221-251","doi":"10.1007/s10107-010-0346-x","url2":"http://dx.doi.org/10.1007/s10107-010-0346-x","abstract":"We perform a smoothed analysis of the GCC-condition number $C(A)$ of the linear programming feasibility problem $∃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.","number":"1-2, Ser. A","bibtex":"@ARTICLE{BA-Robust-Smoothed-Analysis-Of-A-Condition-Number-For-Linear-Programming,\r\n ISSN={0025-5610},\r\n JOURNAL={Mathematical Programming},\r\n TITLE={Robust Smoothed Analysis of a Condition Number for Linear Programming},\r\n VOLUME={131},\r\n AUTHOR={Peter Bürgisser and Dennis Amelunxen},\r\n YEAR={2012},\r\n URL={http://arxiv.org/abs/0803.0925},\r\n PAGES={221-251},\r\n DOI={10.1007/s10107-010-0346-x},\r\n URL2={http://dx.doi.org/10.1007/s10107-010-0346-x},\r\n 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.},\r\n NUMBER={1-2, Ser. A}\r\n}\r\n\r\n","author_short":["Bürgisser, P.","Amelunxen, D."],"key":"BA-Robust-Smoothed-Analysis-Of-A-Condition-Number-For-Linear-Programming","id":"BA-Robust-Smoothed-Analysis-Of-A-Condition-Number-For-Linear-Programming","bibbaseid":"brgisser-amelunxen-robustsmoothedanalysisofaconditionnumberforlinearprogramming-2012","role":"author","urls":{"2":"http://dx.doi.org/10.1007/s10107-010-0346-x","Paper":"http://arxiv.org/abs/0803.0925"},"downloads":0,"html":""},"search_terms":["robust","smoothed","analysis","condition","number","linear","programming","bürgisser","amelunxen"],"keywords":[],"authorIDs":[],"dataSources":["mFLw2PzriqAWWFuqX"]}