Skip to main content
Log in

A polynomial-time algorithm, based on Newton's method, for linear programming

  • Published:
Mathematical Programming Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. Aho, J. Hopcroft and J. Ullman,The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974).

    Google Scholar 

  2. 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).

    Google Scholar 

  3. L. Blum, talk at Workshop on Problems Relating Numerical Analysis to Computer Science, Mathematical Sciences Research Institute, Berkeley, California (January 1986).

  4. L. Blum, “Towards an asymptotic analysis of Karmarkar's algorithm,”Information Processing Letters 23 (1986) 189–194.

    Google Scholar 

  5. 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.

    Google Scholar 

  6. 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.

    Google Scholar 

  7. L.G. Khachiyan, “A polynomial algorithm in linear programming,”Soviet Mathematics Doklady 20 (1979) pp. 191–194.

    Google Scholar 

  8. L.G. Khachiyan, “Polynomial algorithms in linear programming,”USSR Computational Mathematics and Mathematical Physics 20 (1980) pp. 53–72.

    Google Scholar 

  9. J. Lagarias, talk at Mathematical Sciences Research Institute (Berkeley, California, December, 1985).

    Google Scholar 

  10. N. Megiddo and M. Shub, “Boundary behavior of interior point algorithms in linear programming,” Research Report RJ5319, IBM Thomas J. Watson Research Center (1986).

  11. S. Smale, “On the efficiency of algorithms of analysis,”Bulletin of the American Mathematical Society 13 (1985) pp. 87–121.

    Google Scholar 

  12. S. Smale, “Algorithms for solving equations,” to appear in:Proceedings, International Congress of Mathematicians (Berkeley, 1986).

  13. 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.

  14. 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.

  15. 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).

    Google Scholar 

  16. J.H. Wilkinson,The algebraic Eigenvalue Problem (Oxford University Press, Oxford, 1965).

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

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

Reprints 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

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01580724

Key words

Navigation