POLYNOMIAL AFFINE ALGORITHMS FOR LINEAR-PROGRAMMING

被引：27

作者：

GONZAGA, CC

机构：

[1] Department of Systems Engineering and Computer Sciences, COPPE-Federal University of Rio de Janeiro, Rio de Janeiro, 21941, RJ

来源：

MATHEMATICAL PROGRAMMING | 1990年 / 49卷 / 01期

关键词：

affine algorithms; interior methods; Karmarkar's algorithm; Linear programming;

D O I：

10.1007/BF01588776

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The method of steepest descent with scaling (affine scaling) applied to the potential function q log c′x - ∑i=1n log xi solves the linear programming problem in polynomial time for q ≥ n. If q = n, then the algorithm terminates in no more than O(n2L) iterations; if q ≥ n + {Mathematical expression} with q = O(n) then it takes no more than O(nL) iterations. A modified algorithm using rank-1 updates for matrix inversions achieves respectively O(n4L) and O(n3.5L) arithmetic computions. © 1990 The Mathematical Programming Society, Inc.

引用

页码：7 / 21

页数：15