TY - JOUR
T1 - Probabilistic analysis of condition numbers for linear programming
AU - Cheung, D.
AU - Cucker, F.
PY - 2002/7
Y1 - 2002/7
N2 - In this paper, we provide bounds for the expected value of the log of the condition number {\cal C}(A) of a linear feasibility problem given by a n × m matrix A (Ref. 1). We show that this expected value is {\cal O}(min{n, m log n}) if n > m and is {\cat O}(log n) otherwise. A similar bound applies for the log of the condition number C R(A) introduced by Renegar (Ref. 2).
AB - In this paper, we provide bounds for the expected value of the log of the condition number {\cal C}(A) of a linear feasibility problem given by a n × m matrix A (Ref. 1). We show that this expected value is {\cal O}(min{n, m log n}) if n > m and is {\cat O}(log n) otherwise. A similar bound applies for the log of the condition number C R(A) introduced by Renegar (Ref. 2).
KW - condition numbers
KW - linear programming
KW - probabilistic analysis of algorithms
UR - http://www.scopus.com/inward/record.url?scp=0036262238&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0036262238&origin=recordpage
U2 - 10.1023/A:1015460004163
DO - 10.1023/A:1015460004163
M3 - 21_Publication in refereed journal
VL - 114
SP - 55
EP - 67
JO - Journal of Optimization Theory and Applications
JF - Journal of Optimization Theory and Applications
SN - 0022-3239
IS - 1
ER -