Probabilistic Analysis of Condition Numbers for Linear Programming |
| |
| Authors: | Cheung D Cucker F |
| |
| Institution: | (1) Department of Mathematics, City University of Hong Kong, Kowloon, Hong Kong, PRC;(2) Department of Mathematics, City University of Hong Kong, Kowloon, Hong Kong, PRC |
| |
| Abstract: | In this paper, we provide bounds for the expected value of the log of the condition number C(A) of a linear feasibility problem given by a n × m matrix A (Ref. 1). We show that this expected value is O(min{n, m log n}) if n > m and is O(log n) otherwise. A similar bound applies for the log of the condition number C
R(A) introduced by Renegar (Ref. 2). |
| |
| Keywords: | linear programming condition numbers probabilistic analysis of algorithms |
| 本文献已被 SpringerLink 等数据库收录！ |
|
