User menu

Strict Monotonicity and Improved Complexity in the Standard Form Projective Algorithm for Linear-programming

Bibliographic reference Anstreicher, KM.. Strict Monotonicity and Improved Complexity in the Standard Form Projective Algorithm for Linear-programming. In: Mathematical Programming, Vol. 62, no. 3, p. 517-535 (1993)
Permanent URL http://hdl.handle.net/2078.1/49203
  1. K.M. Anstreicher, “A monotonic projective algorithm for fractional linear programming,”Algorithmica 1 (1986a) 483–498.
  2. K.M. Anstreicher, “A strengthened acceptance criterion for approximate projections in Karmarkar's algorithm,”Operations Research Letters 5 (1986b) 211–214.
  3. K.M. Anstreicher and R.A. Bosch, “Long steps in an O(n 3 L) algorithm for linear programming,”Mathematical Programming 54 (1992) 251–265.
  4. K.M. Anstreicher and P. Watteyne, “A family of search directions for Karmarkar's algorithm,” Discussion Paper 9030, Center for Operations Research and Econometrics, Université Catholoque de Louvain (Louvain-la-Neuve, Belgium, 1990).
  5. G. de Ghellinck and J.-P. Vial, “A polynomial Newton method for linear programming,”Algorithmica 1 (1986) 425–453.
  6. C. Fraley and J.-P. Vial, “Single-phase versus multi-phase projective methods for linear programming,” COMIN, University of Geneva (Geneva, Switzerland, 1989).
  7. R.M. Freund, “Projective transformations for interior point methods, part I: basic theory and linear programming,” Working Paper 179-88, OR Center, MIT (Cambridge, MA, 1988).
  8. R.M. Freund, “Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function,”Mathematical Programming 51 (1991) 203–222.
  9. D.M. Gay, “A variant of Karmarkar's linear programming algorithm for problems in standard form,”Mathematical Programming 37 (1987) 81–90.
  10. C.C. Gonzaga, “Conical projection algorithms for linear programming,”Mathematical Programming 43 (1989) 151–173.
  11. C.C. Gonzaga, “Large step path-following methods for linear programming, part I: barrier function method,”SIAM Journal on Optimization 1 (1991a), 268–279.
  12. C.C. Gonzaga, “Large step path-following methods for linear programming, part II: potential reduction method,”SIAM Journal on Optimization 1 (1991b), 280–292.
  13. B. Kalantari, “Karmarkar's algorithm with improved steps,”Mathematical Programming 46 (1990), 73–78.
  14. N. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
  15. M. Padberg, “A different convergence proof of the projective method for linear programming,”Operations Research Letters 4 (1986) 253–257.
  16. J. Renegar, “A polynomial-time algorithm, based on Newton's method, for linear programming,”Mathematical Programming 40 (1988) 59–93.
  17. C. Roos and J.-P. Vial, “Long steps with the logarithmic penalty barrier function in linear programming,” in: J. Gabszewicz, J.-F. Richard and L. Wolsey, eds.Economic Decision Making:Games, Econometrics and Optimisation. Contributions in Honour of Jacques H. Drèze (Elsevier, Amsterdam, 1990) pp. 433–441.
  18. A. Schrijver,Theory of Linear and Integer Programming (Wiley, New York, 1986).
  19. D. Shaw and D. Goldfarb, “A path-following projective interior point method for linear programming,” (1990), to appear in:SIAM Journal on Optimization.
  20. 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).
  21. M.J. Todd, “The effect of sparsity, degeneracy, and null and unbounded variables on variants of Karmarkar's linear programming algorithm,” Technical Report 857, School of OR/IE, Cornell University (Ithaca, NY, 1989).
  22. M.J. Todd and B.P. Burrell, “An extension of Karmarkar's algorithm for linear programming using dual variables,”Algorithmica 1 (1986) 409–424.
  23. M.J. Todd and Y. Ye, “A centered projective algorithm for linear programming,”Mathematics of Operations Research 15 (1990) 508–529.
  24. Y. Ye, “A class of projective transformations for linear programming,”SIAM Journal on Computing 19 (1990) 457–466.
  25. Y. Ye, “An O(n 3 L) potential reduction algorithm for linear programming,”Mathematical Programming 50 (1991) 239–258.
  26. Y. Ye and M. Kojima, “Recovering optimal solutions in Karmarkar's polynomial algorithm for linear programming,”Mathematical Programming 39 (1987) 305–317.