AN EXTENSION OF KARMARKAR ALGORITHM FOR SOLVING A SYSTEM OF LINEAR HOMOGENEOUS EQUATIONS ON THE SIMPLEX

被引：11

作者：

DEGHELLINCK, G ^{[1
]}

VIAL, JP ^{[1
]}

机构：

[1] UNIV GENEVA,FAC SES,CH-1211 GENEVA 4,SWITZERLAND

来源：

MATHEMATICAL PROGRAMMING | 1987年 / 39卷 / 01期

关键词：

COMPUTER PROGRAMMING - Algorithms - OPTIMIZATION;

D O I：

10.1007/BF02592072

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present an extension of Karmarkar's algorithm for solving a system of linear homogeneous equations onthe simplex. It is shown that inat most O(nL) steps, the algorithm produces a feasible point or proves that the problem has no solution. The complexity is O(m**2m**2L) arithmetic operations. The algorithm is endowed with two new powerful stopping criteria.

引用

页码：79 / 92

页数：14

共 4 条

[1] A Monotonic Projective Algorithm for Fractional Linear Programming
Anstreicher, Kurt M.
[J]. ALGORITHMICA, 1986, 1 (1-4) : 483 - 498
[2] APSVALL B, 1980, J ALGORITHMS, V1, P1
[3] A Polynomial Newton Method for Linear Programming
de Ghellinck, Guy
Vial, Jean-Philippe
[J]. ALGORITHMICA, 1986, 1 (1-4) : 425 - 453
[4] An Extension of Karmarkar's Algorithm for Linear Programming Using Dual Variables
Todd, Michael J.
Burrell, Bruce P.
[J]. ALGORITHMICA, 1986, 1 (1-4) : 409 - 424

← 1 →