Solving linear programs with finite precision: I. Condition numbers and random programs

• 成果类型: Article
• 署名作者: Cheung, D; Cucker, F
• 署名单位: City University of Hong Kong
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-003-0393-7
• 发表日期: 2004
• 页码: 175-196
• 关键词: probabilistic analysis; Complexity theory

摘要

We define a condition number K(A,b,c) for a linear program min c(T)x s.t. Ax=b,xgreater than or equal to0 and give two characterizations via distances to degeneracy and singularity. We also give bounds for the expected value, as well as for higher moments, of log K(A,b,c) when the entries of A,b and c are i.i.d. random variables with normal distribution.