A CLASS OF PROJECTIVE TRANSFORMATIONS FOR LINEAR-PROGRAMMING

被引：24
作者：
YE, YY
机构：
[1] Univ of Iowa, , IA
来源：
SIAM JOURNAL ON COMPUTING | 1990年 / 19卷 / 03期
关键词：
Computer Programming--Algorithms;
D O I：
10.1137/0219030
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A class of projective transformations under which potential functions are invariant for linear programming is described. As a result, a new projective algorithm converging in O(L√n) iterations is developed. The algorithm does not require centering conditions, and its convergence speed is improved by a factor √n over Karmarkar's projective algorithm and by a constant over the recent affine potential reduction algorithm.
引用
收藏
页码：457 / 466
页数：10
相关论文
共 18 条
[1]  
[Anonymous], 2003, LINEAR PROGRAMMING
[2]   A Monotonic Projective Algorithm for Fractional Linear Programming [J].
Anstreicher, Kurt M. .
ALGORITHMICA, 1986, 1 (1-4) :483-498
[3]  
BAYER D, 1987, NONLINEAR GEOMETRY L, V1
[4]  
BAYER D, IN PRESS T AM MATH S
[5]   A Polynomial Newton Method for Linear Programming [J].
de Ghellinck, Guy ;
Vial, Jean-Philippe .
ALGORITHMICA, 1986, 1 (1-4) :425-453
[6]  
FREUND R. M., 1988, POLYNOMIAL TIME ALGO
[7]   A VARIANT OF KARMARKAR LINEAR-PROGRAMMING ALGORITHM FOR PROBLEMS IN STANDARD FORM [J].
GAY, DM .
MATHEMATICAL PROGRAMMING, 1987, 37 (01) :81-90
[8]  
GONZAGA CC, 1987, UCBERL M8711 U CAL E
[9]   A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING [J].
KARMARKAR, N .
COMBINATORICA, 1984, 4 (04) :373-395
[10]  
Megiddo N., 1989, PROGR MATH PROGRAMMI, P131, DOI DOI 10.1007/978-1-4613-9617-8_8
12