CONVERGENCE BEHAVIOR OF KARMARKAR PROJECTIVE ALGORITHM FOR SOLVING A SIMPLE LINEAR PROGRAM

被引：3

作者：

KALISKI, JA

YE, YY

机构：

[1] Department of Management Sciences, The University of Iowa, Iowa City

来源：

OPERATIONS RESEARCH LETTERS | 1991年 / 10卷 / 07期

关键词：

LINEAR PROGRAMMING; KARMARKAR ALGORITHM;

D O I：

10.1016/0167-6377(91)90040-V

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 [运筹学与控制论]; 12 [管理学]; 1201 [管理科学与工程]; 1202 [工商管理学]; 120202 [企业管理];

摘要：

We describe the convergence behavior of Karmarkar's projective algorithm for solving a simple linear program. We show that the algorithm requires at least n - 1 iterations to reach the optimal solution, while the simplex method may need one pivot step. Thus in the worst case, Karmarkar's algorithm will require at least OMEGA(n) iterations to converge.

引用

页码：389 / 393

页数：5

共 6 条

[1]

THE WORST-CASE STEP IN KARMARKAR ALGORITHM [J].