Improved complexity results on solving real-number linear feasibility problems

• 成果类型: Article
• 署名作者: Ye, YY
• 署名单位: Stanford University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0610-7
• 发表日期: 2006
• 页码: 339-363
• 关键词: polynomial-time algorithm; interior-point algorithms; path; variant

摘要

We present complexity results on solving real-number standard linear programs LP(A, b, c), where the constraint matrix A is an element of R-m x n, the right-hand-side vector b is an element of R-m and the objective coefficient vector c is an element of R-n are real. In particular, we present a two-layered interior-point method and show that LP(A, b, 0), i.e., the linear feasibility problem Ax = b and x >= 0, can be solved in in O(n(2.5)c(A)) interior-point method iterations. Here 0 is the vector of all zeros and c(A) is the condition measure of matrix A defined in [25]. This complexity iteration bound is reduced by a factor n from that for general LP(A, b, c) in [ 25]. We also prove that the iteration bound will be further reduced to O(n(1.5)c(A)) for LP(A, 0, 0), i.e., for the homogeneous linear feasibility problem. These results are surprising since the classical view has been that linear feasibility would be as hard as linear programming.