Probabilistic analysis of condition numbers for linear programming
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 55-67 |
| Journal / Publication | Journal of Optimization Theory and Applications |
| Volume | 114 |
| Issue number | 1 |
| Publication status | Published - Jul 2002 |
Link(s)
Abstract
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).
Research Area(s)
- condition numbers, linear programming, probabilistic analysis of algorithms
Citation Format(s)
Probabilistic analysis of condition numbers for linear programming. / Cheung, D.; Cucker, F.
In: Journal of Optimization Theory and Applications, Vol. 114, No. 1, 07.2002, p. 55-67.
In: Journal of Optimization Theory and Applications, Vol. 114, No. 1, 07.2002, p. 55-67.
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
