AN ALGORITHM FOR LINEAR-PROGRAMMING WHICH REQUIRES O(((M+N)N2+(M+N)1.5N)L) ARITHMETIC OPERATIONS

被引：104

作者：

VAIDYA, PM

机构：

[1] AT and T Bell Laboratories, 07974, NJ, Murray Hill

来源：

MATHEMATICAL PROGRAMMING | 1990年 / 47卷 / 02期

关键词：

complexity; linear programming; Optimization; polynomial time algorithms;

D O I：

10.1007/BF01580859

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present an algorithm for linear programming which requires O(((m+n)n2+(m+n)1.5n)L) arithmetic operations where m is the number of constraints, and n is the number of variables. Each operation is performed to a precision of O(L) bits. L is bounded by the number of bits in the input. The worst-case running time of the algorithm is better than that of Karmarkar's algorithm by a factor of {Mathematical expression}. © 1990 The Mathematical Programming Society, Inc.

引用

页码：175 / 201

页数：27

共 13 条

[1]

[Anonymous], 1980, USSR COMP MATH MATH+, DOI [DOI 10.1016/0041-5553(80)90061-0, 10.1016/0041-5553(80)90061-0]

[2]

BAYER DA, 1989, IN PRESS T AM MATH S

[3] SYSTEMS OF DISTINCT REPRESENTATIVES AND LINEAR ALGEBRA [J].

EDMONDS, J .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICAL SCIENCES, 1967, B 71 (04) :241-+

[4]

GANTMACHER FR, 1959, MATRIX THEORY, V1, pCH2

[5]

GONZAGA C, 1987, UCBERL M8710 U BERK

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

KARMARKAR, N .

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

[7]

Papadimitriou C. H., 1998, COMBINATORIAL OPTIMI

[8] A POLYNOMIAL-TIME ALGORITHM, BASED ON NEWTON METHOD, FOR LINEAR-PROGRAMMING [J].

RENEGAR, J .

MATHEMATICAL PROGRAMMING, 1988, 40 (01) :59-93

[9]

SONNEVAND G, 1989, ANAL CTR POLYHEDRONS, P6

[10]

Stewart GW, 1973, INTRO MATRIX COMPUTA

← 1 2 →