Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems |
| |
| Authors: | Michael J Todd Levent Tunçel Yinyu Ye |
| |
| Institution: | (1) School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York 14853, USA, e-mail: miketodd@cs.cornell.edu., US;(2) Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada, e-mail: ltuncel@math.uwaterloo.ca., CA;(3) Department of Management Sciences, The University of Iowa, Iowa City, IA 52242, USA, e-mail: yinyu-ye@uiowa.edu., US |
| |
| Abstract: | This note studies
A
, a condition number used in the linear programming algorithm of Vavasis and Ye 14] whose running time depends only on the
constraint matrix A∈ℝ
m×n
, and (A), a variant of another condition number due to Ye 17] that also arises in complexity analyses of linear programming problems.
We provide a new characterization of
A
and relate
A
and (A). Furthermore, we show that if A is a standard Gaussian matrix, then E(ln
A
)=O(min{mlnn,n}). Thus, the expected running time of the Vavasis-Ye algorithm for linear programming problems is bounded by a polynomial
in m and n for any right-hand side and objective coefficient vectors when A is randomly generated in this way. As a corollary of the close relation between
A
and (A), we show that the same bound holds for E(ln(A)).
Received: September 1998 / Accepted: September 2000?Published online January 17, 2001 |
| |
| Keywords: | : linear programming – interior-point methods – probabilistic analysis |
| 本文献已被 SpringerLink 等数据库收录！ |
|
