Long steps in an O(n ³ L) algorithm for linear programming

• K.M. Anstreicher, “A monotonic projective algorithm for fractional linear programming,”Algorithmica 1 (1986) 483–498.

  Google Scholar 

• K.M. Anstreicher, “A standard form variant, and safeguarded linesearch, for the modified Karmarkar algorithm,”Mathematical Programming 47 (1990) 337–351.

  Google Scholar 

• E.R. Barnes, “A variation on Karmarkar's algorithm for solving linear programming problems,”Mathematical Programming 36 (1986) 174–182.

  Google Scholar 

• E.R. Barnes, S. Chopra and D. Jensen, “A polynomial-time version of the affine scaling algorithm,” IBM Watson Research Center (Yorktown Heights, NY, 1988).

  Google Scholar 

• D.A. Bayer and J.C. Lagarias, “The nonlinear geometry of linear programming,”American Mathematical Society 314 (1989) 499–581.

  Google Scholar 

• I.I. Dikin, “Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675.

  Google Scholar 

• R.M. Freund, “Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function,” Sloan School, M.I.T. (Cambridge, MA, 1988).

  Google Scholar 

• D.M. Gay, “A variant of Karmarkar's linear programming algorithm for problems in standard form,”Mathematical Programming 37 (1987) 81–90.

  Google Scholar 

• C.C. Gonzaga, “An algorithm for solving linear programming problems in O(n ³ L) operations,” in: N. Megiddo, ed.Progress in Mathematical Programming (Springer, Berlin, 1989a) pp. 1–28.

  Google Scholar 

• C.C. Gonzaga, “Conical projection algorithms for linear programming,”Mathematical Programming 43 (1989b) 151–173.

  Google Scholar 

• C.C. Gonzaga, “Large-step path-following methods for linear programming, Part II: potential reduction method,”SIAM Journal on Optimization 1 (1991a) 280–292.

  Google Scholar 

• C.C. Gonzaga, “Polynomial affine algorithms for linear programming,”Mathematical Programming 49 (1991b) 7–21.

  Google Scholar 

• N. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.

  Google Scholar 

• N. Megiddo and M. Shub, “Boundary behavior of interior point algorithms in linear programming,”Mathematics of Operations Research 14 (1989) 97–146.

  Google Scholar 

• R.C. Monteiro and I. Adler, “Interior path following primal—dual algorithms. Part I: linear programming,”Mathematical Programming 44 (1989) 27–41.

  Google Scholar 

• R.C. Monteiro, I. Adler and M.C. Resende, “A polynomial-time primal—dual affine scaling algorithm for linear and convex quadratic programming and its power series extension,”Mathematics of Operations Research 15 (1990) 191–214.

  Google Scholar 

• J. Renegar, “A polynomial-time algorithm, based on Newton's method, for linear programming,”Mathematical Programming 40 (1988) 59–93.

  Google Scholar 

• D.F. Shanno, “Computing Karmarkar projections quickly,”Mathematical Programming 41 (1988) 61–71.

  Google Scholar 

• G. Sonnevend, “An analytical centre for a polyhedron and new classes of global algorithms for linear (smooth, convex) programming,”Proceedings of the 12th IFIP Conference on System Modeling (Budapest, 1985).

• A.E. Steger, “An extension of Karmarkar's algorithm for bounded linear programming problems,” M.S. Thesis, State University of New York (Stonybrook, NY, 1985).

  Google Scholar 

• M.J. Todd and Y. Ye, “A centred projective algorithm for linear programming,”Mathematics of Operations Research 15 (1990) 508–529.

  Google Scholar 

• P.M. Vaidya, “An algorithm for linear programming which requires O(((m+n)n ²+(m+n)^1.5 n)L) arithmetic operations,”Mathematical Programming 47 (1990) 175–201.

  Google Scholar 

• R.J. Vanderbei and J.C. Lagarias, “I.I. Dikin's convergence result for the affine-scaling algorithm,” AT&T Bell Laboratories (Murray Hill, NJ, 1988).

  Google Scholar 

• R.J. Vanderbei, M.J. Meketon and B.A. Freedman, “A modification of Karmarkar's linear programming algorithm,”Algorithmica 1 (1986) 395–407.

  Google Scholar 

• Y. Ye, “An O(n ³ L) potential reduction algorithm for linear programming,”Mathematical Programming 50 (1991) 239–258.

  Google Scholar 

• Y. Ye and M. Kojima, “Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming,”Mathematical Programming 39 (1987) 305–317.

  Google Scholar 

Download references