Abstract
A new interior method for linear programming is presented and a polynomial time bound for it is proven. The proof is substantially different from those given for the ellipsoid algorithm and for Karmarkar's algorithm. Also, the algorithm is conceptually simpler than either of those algorithms.
Similar content being viewed by others
References
A. Aho, J. Hopcroft and J. Ullman,The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974).
D.A. Bayer and J.C. Lagarias, “The non-linear geometry of linear programming, I. Affine and projective scaling trajectories, II. Legendre transform coordinates, III. Central trajectories,” preprints, AT&T Bell Laboratories (Murray Hill, NJ, 1986).
L. Blum, talk at Workshop on Problems Relating Numerical Analysis to Computer Science, Mathematical Sciences Research Institute, Berkeley, California (January 1986).
L. Blum, “Towards an asymptotic analysis of Karmarkar's algorithm,”Information Processing Letters 23 (1986) 189–194.
P. Huard, “Resolution of mathematical programming with non-linear constraints by the method of centers,” in: J. Abadie, ed.,Non-Linear Programming (North-Holland, Amsterdam, 1967) pp. 207–219.
N. Karmarkar, “A new polynomial-time algorithm for linear programming,” in:Proceedings of the 16th Annual ACM Symposium on Theory of Computing (1984), ACM, New York, 1984, pp. 302–311; revised version:Combinatorica 4 (1984) pp. 373–395.
L.G. Khachiyan, “A polynomial algorithm in linear programming,”Soviet Mathematics Doklady 20 (1979) pp. 191–194.
L.G. Khachiyan, “Polynomial algorithms in linear programming,”USSR Computational Mathematics and Mathematical Physics 20 (1980) pp. 53–72.
J. Lagarias, talk at Mathematical Sciences Research Institute (Berkeley, California, December, 1985).
N. Megiddo and M. Shub, “Boundary behavior of interior point algorithms in linear programming,” Research Report RJ5319, IBM Thomas J. Watson Research Center (1986).
S. Smale, “On the efficiency of algorithms of analysis,”Bulletin of the American Mathematical Society 13 (1985) pp. 87–121.
S. Smale, “Algorithms for solving equations,” to appear in:Proceedings, International Congress of Mathematicians (Berkeley, 1986).
Gy. Sonnevend, “A new method for solving a set of linear (convex) inequalities and its applications for identification and optimization,” preprint, Department of Numerical Analysis, Institute of Mathematics, Eötvös University, 1088, Budapest, Muzeum Körut 6–8.
Gy. Sonnevend, “An analytical centre' for polyhedrons and new classes of global algorithms for linear (smooth convex) programming,” preprint, Department of Numerical Analysis, Institute of Mathematics, Eötvös University, 1088, Budapest, Muzeum Körut 6–8.
P. Vaidya, “An algorithm for linear programming which requires O((m+n)n 2+(m+n)1.5 n)L) arithmetic operations,” AT&T Bell Laboratories, Murray Hill, NJ (1987).
J.H. Wilkinson,The algebraic Eigenvalue Problem (Oxford University Press, Oxford, 1965).
Author information
Authors and Affiliations
Additional information
This research was supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship and by NSF Grant 8120790. The research was performed at the Mathematical Sciences Research Institute in Berkeley, California.
Rights and permissions
About this article
Cite this article
Renegar, J. A polynomial-time algorithm, based on Newton's method, for linear programming. Mathematical Programming 40, 59–93 (1988). https://doi.org/10.1007/BF01580724
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01580724