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

共 14 条

[1]

BAYER DA, 1986, NONLINEAR GEOMETRY L, V1

[2]

BAYER DA, 1986, NONLINEAR GEOMETRY L, V2

[3]

BAYER DA, 1986, NONLINEAR GEOMETRY L, V3

[4] CONICAL PROJECTION ALGORITHMS FOR LINEAR-PROGRAMMING [J].

GONZAGA, CC .

MATHEMATICAL PROGRAMMING, 1989, 43 (02) :151-173

[5]

GONZAGA CC, 1988, PROGR MATH PROGRAMMI, P1

[6] A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING [J].

KARMARKAR, N .

COMBINATORICA, 1984, 4 (04) :373-395

[7]

KOJIMA M., 1988, PROGR MATH PROGRAMMI, P29

[8]

MEGIDDO N, 1986, RJ5319 IBM TJ WATS R

[9]

MEGIDDO N, 1987, ADV EC THEORY, P225

[10]

MONTEIRO RC, 1987, UNPUB ON3L PRIMAL DU

← 1 2 →