A Low Complexity Interior-Point Algorithm for Linear Programming
- 1 May 1992
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 2 (2) , 198-209
- https://doi.org/10.1137/0802011
Abstract
This paper describes an interior-point algorithm for linear programming that is almost as simple as the affine-scaling method and yet achieves the currently best complexity of O(root n t) iterations to attain precision t. The basic algorithm needs neither dual estimates nor lower bounds, although its analysis is based on Ye's results for the primal-dual potential function. Some computationally preferable variants are also presented.Keywords
This publication has 22 references indexed in Scilit:
- Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential functionMathematical Programming, 1991
- On monotonicity in the scaled potential algorithm for linear programmingLinear Algebra and its Applications, 1991
- Search directions for interior linear-programming methodsAlgorithmica, 1991
- Large Step Path-Following Methods for Linear Programming, Part II: Potential Reduction MethodSIAM Journal on Optimization, 1991
- Polynomial affine algorithms for linear programmingMathematical Programming, 1990
- An Algorithm for Solving Linear Programming Problems in O(n 3 L) OperationsPublished by Springer Nature ,1989
- A monotonic projective algorithm for fractional linear programmingAlgorithmica, 1986
- A polynomial newton method for linear programmingAlgorithmica, 1986
- A variation on Karmarkar’s algorithm for solving linear programming problemsMathematical Programming, 1986
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984