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 [J].