Template-Type: ReDIF-Paper 1.0
Author-Name: Sturm, J.F.
Author-Name-Last: Sturm
Author-Name: Zhang, S.
Author-Name-Last: Zhang
Author-Name-First: Shuzhong
Title: An interior point method, based on rank-one updates, for linear programming
Abstract: We propose a polynomial time primal-dual potential reduction algorithm for linear programming. Unlike any other interior point method, the new algorithm is based on a rank-one updating scheme for sequentially computing the projection matrices. For a standard linear programming problem, the number of operations required is [TeX: ${\\cal O}(mn)$] per main iteration and the overall computational complexity is [TeX: ${\\cal O}(mn^{2.5}L)$].
Creation-Date: 1995-01-01
Series: RePEc:ems:eureir
Number: EI 9546-/A
Keywords: interior point method, linear programming, potential function
Handle: RePEc:ems:eureir:1360