{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T19:41:40Z","timestamp":1771530100752,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1997,1]]},"DOI":"10.1007\/bf02614377","type":"journal-article","created":{"date-parts":[[2007,4,28]],"date-time":"2007-04-28T04:38:07Z","timestamp":1177735087000},"page":"3-45","source":"Crossref","is-referenced-by-count":8,"title":["Potential-reduction methods in mathematical programming"],"prefix":"10.1007","volume":"76","author":[{"given":"Michael J.","family":"Todd","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02614377_CR1","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1007\/BF01840458","volume":"1","author":"K.M. Anstreicher","year":"1986","unstructured":"K.M. Anstreicher, \u201cA monotonic projective algorithm for fractional linear programming,\u201dAlgorithmica 1 (1986) 483\u2013498.","journal-title":"Algorithmica"},{"key":"BF02614377_CR2","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01582290","volume":"43","author":"K.M. Anstreicher","year":"1989","unstructured":"K.M. Anstreicher, \u201cA combined phase I-phase II projective algorithm for linear programming,\u201dMathematical Programming 43 (1989) 209\u2013223.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR3","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/BF01582899","volume":"52","author":"K.M. Anstreicher","year":"1991","unstructured":"K.M. Anstreicher, \u201cA combined phase I-phase II scaled potential algorithm for linear programming.\u201dMathematical Programming 52 (1991) 429\u2013439.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR4","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1137\/0801003","volume":"1","author":"K.M. Anstreicher","year":"1991","unstructured":"K.M. Anstreicher, \u201cOn the performance of Karmarkar\u2019s algorithm over a sequence of iterations,\u201dSIAM Journal on Optimization 1 (1991) 22\u201329.","journal-title":"SIAM Journal on Optimization"},{"key":"BF02614377_CR5","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0167-6377(92)90026-Y","volume":"11","author":"K.M. Anstreicher","year":"1992","unstructured":"K.M. Anstreicher, \u201cOn interior algorithms for linear programming with no regularity assumptions,\u201dOperations Research Letters 11 (1992) 209\u2013212.","journal-title":"Operations Research Letters"},{"key":"BF02614377_CR6","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/BF01594941","volume":"50","author":"D.A. Bayer","year":"1991","unstructured":"D.A. Bayer and J.C. Lagarias, \u201cKarmarkar\u2019s linear programming algorithm and Newton\u2019s method,\u201dMathematical Programming 50 (1991) 291\u2013330.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR7","series-title":"Working Paper","volume-title":"On the worst case complexity of potential reduction algorithms for linear programming","author":"D. Bertsimas","year":"1993","unstructured":"D. Bertsimas and X. Luo, \u201cOn the worst case complexity of potential reduction algorithms for linear programming,\u201d Working Paper 3558-93. Sloan School of Management, MIT, Cambridge, MA 02139, USA (1993)."},{"key":"BF02614377_CR8","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/BF01188712","volume":"9","author":"R.A. Bosch","year":"1993","unstructured":"R.A. Bosch and K.M. Anstreicher, \u201cOn partial updating in a potential reduction linear programming algorithm of Kojima, Mizuno and Yoshise,\u201dAlgorithmica 9 (1993) 184\u2013197.","journal-title":"Algorithmica"},{"key":"BF02614377_CR9","volume-title":"The Linear Complementarity Problem","author":"R.W. Cottle","year":"1992","unstructured":"R.W. Cottle, J.-S. Pang, and R.E. Stone,The Linear Complementarity Problem (Academic Press, Boston, MA, 1992)."},{"key":"BF02614377_CR10","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF01586933","volume":"51","author":"R.M. Freund","year":"1991","unstructured":"R.M. Freund, \u201cPolynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function,\u201dMathematical Programming 51 (1991) 203\u2013222.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR11","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/BF01582900","volume":"52","author":"R.M. Freund","year":"1991","unstructured":"R.M. Freund, \u201cA potential-function reduction algorithm for solving a linear program directly from an infeasible \u2018warm start\u2019,\u201dMathematical Programming 52 (1991) 441\u2013466.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR12","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/BF01840456","volume":"1","author":"G. Ghellinck de","year":"1986","unstructured":"G. de Ghellinck and J.P. Vial, \u201cA polynomial Newton method for linear programming,\u201dAlgorithmica 1 (1986) 425\u2013453.","journal-title":"Algorithmica"},{"key":"BF02614377_CR13","first-page":"141","volume-title":"Optimization, Handbooks in Operations Research and Management Science. itVol. 1","author":"D. Goldfarb","year":"1989","unstructured":"D. Goldfarb and M.J. Todd, \u201cLinear Programming,\u201d in: G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd, eds.,Optimization, Handbooks in Operations Research and Management Science. itVol. 1 (North-Holland, Amsterdam, 1989) pp. 141\u2013170."},{"key":"BF02614377_CR14","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF01588776","volume":"49","author":"C.C. Gonzaga","year":"1990","unstructured":"C.C. Gonzaga, \u201cPolynomial affine algorithms for linear programming,\u201dMathematical Programming 49 (1990) 7\u201321.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR15","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1137\/0801019","volume":"1","author":"C.C. Gonzaga","year":"1991","unstructured":"C.C. Gonzaga, \u201cLarge steps path-following methods for linear programming, Part II: Potential reduction method,\u201dSIAM Journal on Optimization 1 (1991) 280\u2013292.","journal-title":"SIAM Journal on Optimization"},{"key":"BF02614377_CR16","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1137\/1034048","volume":"34","author":"C.C. Gonzaga","year":"1992","unstructured":"C.C. Gonzaga, \u201cPath following methods for linear programming,\u201dSIAM Review 34 (1992) 167\u2013227.","journal-title":"SIAM Review"},{"key":"BF02614377_CR17","volume-title":"Barrier functions in interior-point methods","author":"O. G\u00fcler","year":"1994","unstructured":"O. G\u00fcler, \u201cBarrier functions in interior-point methods,\u201d Department of Mathematics and Statistics, University of Maryland Baltimore County. Baltimore, MD (1994) to appear in:Mathematics of Operation Research."},{"key":"BF02614377_CR18","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01580721","volume":"40","author":"H. Imai","year":"1988","unstructured":"H. Imai, \u201cOn the convexity of the multiplicative version of Karmarkar\u2019s potential function,\u201dMathematical Programming 40 (1988) 29\u201332.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR19","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1137\/0804028","volume":"4","author":"J. Ji","year":"1994","unstructured":"J. Ji and Y. Ye, \u201cA complexity analysis for interior-point algorithms based on Karmarkar\u2019s potential function,\u201dSIAM Journal on Optimization 4 (1994) 512\u2013520.","journal-title":"SIAM Journal on Optimization"},{"key":"BF02614377_CR20","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N.K. Karmarkar","year":"1984","unstructured":"N.K. Karmarkar, \u201cA new polynomial-time algorithm for linear programming,\u201dCombinatorica 4 (1984) 373\u2013395.","journal-title":"Combinatorica"},{"key":"BF02614377_CR21","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/BF01586054","volume":"54","author":"M. Kojima","year":"1992","unstructured":"M. Kojima, N. Megiddo and Y. Ye, \u201cAn interior point potential reduction algorithm for the linear complementarity problem,\u201dMathematical Programming 54 (1992) 267\u2013279.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR22","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/BF01594942","volume":"50","author":"M. Kojima","year":"1991","unstructured":"M. Kojima, S. Mizuno and A. Yoshise, \u201cAn $$O(\\sqrt n L)$$ iteration potential reduction algorithm for linear complementarity problems,\u201dMathematical Programming 50 (1991) 331\u2013342.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR23","unstructured":"E. Kranich, \u201cInterior point methods for mathematical programming: A bibliography,\u201d available through NETLIB: send e-mail to netlib@research.att.com containing the message \u201csend intbib.bib from bib\u201d and\/or \u201csend intbib.bbl from bib.\u201d"},{"key":"BF02614377_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/ijoc.6.1.1","volume":"6","author":"I.J. Lustig","year":"1994","unstructured":"I.J. Lustig, R.E. Marsten, and D.F. Shanno, \u201cInterior point methods: Computational state of the art,\u201dORSA Journal on Computing 6 (1994) 1\u201314.","journal-title":"ORSA Journal on Computing"},{"key":"BF02614377_CR25","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1137\/0804014","volume":"4","author":"K.A. McShane","year":"1994","unstructured":"K.A. McShane, \u201cSuperlinearly convergent $$O(\\sqrt n L)$$ -iteration interior-point algorithms for linear programming and the monotone linear complementarity problem,\u201dSIAM Journal on Optimization 4 (1994) 247\u2013261.","journal-title":"SIAM Journal on Optimization"},{"key":"BF02614377_CR26","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0024-3795(91)90273-Y","volume":"152","author":"S. Mizuno","year":"1991","unstructured":"S. Mizuno, \u201cO(n \u03c1 L) iteration O(n 3 L) potential reduction algorithms for linear programming,\u201dLinear Algebra and its Applications 152 (1991) 155\u2013168.","journal-title":"Linear Algebra and its Applications"},{"key":"BF02614377_CR27","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1137\/0805003","volume":"5","author":"S. Mizuno","year":"1995","unstructured":"S. Mizuno, M. Kojima and M.J. Todd, \u201cInfeasible-interior-point primal dual potential-reduction algorithms for linear programming,\u201dSIAM Journal on Optimization 5 (1995) 52\u201367.","journal-title":"SIAM Journal on Optimization"},{"key":"BF02614377_CR28","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/BF01585163","volume":"62","author":"S. Mizuno","year":"1993","unstructured":"S. Mizuno and A. Nagasawa, \u201cA primal-dual affine scaling potential reduction algorithm for linear programming,\u201dMathematical Programming 62 (1993) 119\u2013131.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR29","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1090\/conm\/114\/1097875","volume-title":"Mathematical Developments Arising from Linear Programming: Proceedings of a Joint Summer Research Conference held at Bowdoin College, Brunswick, Maine, USA, June\/July 1988","author":"R.D.C. Monteiro","year":"1990","unstructured":"R.D.C. Monteiro, \u201cConvergence and boundary behavior of the projective scaling trajectories for linear programming,\u201d in J.C. Lagarias and M.J. Todd, eds.,Mathematical Developments Arising from Linear Programming: Proceedings of a Joint Summer Research Conference held at Bowdoin College, Brunswick, Maine, USA, June\/July 1988, Vol. 114 ofContemporary Mathematics (American Mathematical Society, Providence, RI, 1990) pp. 213\u2013229."},{"key":"BF02614377_CR30","first-page":"311","volume":"69","author":"R.D.C. Monteiro","year":"1995","unstructured":"R.D.C. Monteiro and S.J. Wright, \u201cSuperlinear primal-dual affine scaling algorithms for LCP,\u201dMathematical Programming 69 (1995) 311\u2013333.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR31","unstructured":"J.L. Nazarcth, \u201cQuadratic and conic approximating models in linear programming,\u201dMathematical Programming Society COAL Bulletin 23 (1994)."},{"key":"BF02614377_CR32","volume-title":"Long-step strategies in interior point potential-reduction methods","author":"Yu.E. Nesterov","year":"1993","unstructured":"Yu.E. Nesterov, \u201cLong-step strategies in interior point potential-reduction methods,\u201d Department SES COMIN, Geneva University, Switzerland (1993)."},{"key":"BF02614377_CR33","volume-title":"Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms","author":"Yu.E. Nesterov","year":"1993","unstructured":"Yu.E. Nesterov and A.S. Nemirovskii,Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms (SIAM, Philadelphia, PA, 1993)."},{"key":"BF02614377_CR34","series-title":"Technical Report","first-page":"14853","volume-title":"School of Operations Research and Industrial Engineering","author":"Yu.E. Nesterov","year":"1994","unstructured":"Yu.E. Nesterov and M.J. Todd, \u201cSelf-scaled barriers and interior-point methods for convex programming,\u201d Technical Report No. 1091. School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY 14853\u20133801 (1994) to appear in:Mathematics of Operations Research."},{"key":"BF02614377_CR35","series-title":"Technical Report","first-page":"14853","volume-title":"School of Operations Research and Industrial Engineering","author":"Yu.E. Nesterov","year":"1995","unstructured":"Yu.E. Nesterov and M.J. Todd, \u201cPrimal-dual interior-point methods for self-scaled cones,\u201d Technical Report No. 1125, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY 14853\u20133801 (1995)."},{"key":"BF02614377_CR36","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01585165","volume":"62","author":"M.J.D. Powell","year":"1993","unstructured":"M.J.D. Powell, \u201cOn the number of iterations of Karmarkar\u2019s algorithm for linear programming,\u201dMathematical Programming 62 (1993) 153\u2013197.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR37","series-title":"Lecture Notes in Control and Information Sciences","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/BFb0042787","volume-title":"System Modelling and Optimization: Proceedings of the 13th IFIP Conference, Tokyo, Japan. Aug\/Sept. 1987","author":"K. Tanabe","year":"1988","unstructured":"K. Tanabe, \u201cCentered Newton method for mathematical programming,\u201d in M. Iri and K. Yajima, eds.,System Modelling and Optimization: Proceedings of the 13th IFIP Conference, Tokyo, Japan. Aug\/Sept. 1987, Vol. 113 ofLecture Notes in Control and Information Sciences (Springer-Verlag, Berlin, 1988) pp. 197\u2013206."},{"key":"BF02614377_CR38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01581187","volume":"55","author":"M.J. Todd","year":"1992","unstructured":"M.J. Todd, \u201cOn Anstreicher\u2019s combined phase I-phase II projective algorithm for linear programming,\u201dMathematical Programming 55 (1992) 1\u201315.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR39","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01581241","volume":"59","author":"M.J. Todd","year":"1993","unstructured":"M.J. Todd, \u201cCombining phase I and phase II in a potential reduction algorithm for linear programming,\u201dMathematical Programming 59 (1993) 133\u2013150.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR40","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/BF01840455","volume":"1","author":"M.J. Todd","year":"1986","unstructured":"M.J. Todd and B.P. Burrell, \u201cAn extension of Karmarkar\u2019s algorithm for linear programming using dual variables,\u201dAlgorithmica 1 (1986) 409\u2013424.","journal-title":"Algorithmica"},{"key":"BF02614377_CR41","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1287\/moor.15.3.508","volume":"15","author":"M.J. Todd","year":"1990","unstructured":"M.J. Todd and Y. Ye, \u201cA centered projective algorithm for linear programming,\u201dMathematics of Operations Research 15 (1990) 508\u2013529.","journal-title":"Mathematics of Operations Research"},{"key":"BF02614377_CR42","series-title":"Technical Report","first-page":"14853","volume-title":"School of Operations Research and Industrial Engineering","author":"M.J. Todd","year":"1994","unstructured":"M.J. Todd and Y. Ye, \u201cApproximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming,\u201d Technical Report No. 1109, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY 14853\u20133801 (1994)."},{"key":"BF02614377_CR43","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF01581142","volume":"66","author":"L. Tun\u00e7el","year":"1994","unstructured":"L. Tun\u00e7el, \u201cConstant potential primal dual algorithms: A framework,\u201dMathematical Programming 66 (1994) 145\u2013159.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR44","series-title":"Technical Report","first-page":"14853","volume-title":"School of Operations Research and Industrial Engineering","author":"R.H. T\u00fct\u00fcnc\u00fc","year":"1995","unstructured":"R.H. T\u00fct\u00fcnc\u00fc, \u201cA practical infeasible-interior-point potential-reduction algorithm for linear programming,\u201d Technical Report No. 1136, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY 14853\u20133801 (1995)."},{"key":"BF02614377_CR45","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L. Vandenberghe","year":"1996","unstructured":"L. Vandenberghe and S. Boyd, \u201cSemidefinite programming,\u201dSIAM Review 38 (1996) 49\u201395.","journal-title":"SIAM Review"},{"key":"BF02614377_CR46","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF01594937","volume":"50","author":"Y. Ye","year":"1991","unstructured":"Y. Ye, \u201cAn O(n 3 L) potential reduction algorithm for linear programming,\u201dMathematical Programming 50 (1991) 239\u2013258.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR47","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1137\/0802002","volume":"2","author":"Y. Ye","year":"1992","unstructured":"Y. Ye, \u201cA potential reduction algorithm allowing column generation,\u201dSIAM Journal on Optimization 2 (1992) 7\u201320.","journal-title":"SIAM Journal on Optimization"},{"key":"BF02614377_CR48","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF01581269","volume":"58","author":"Y. Ye","year":"1993","unstructured":"Y. Ye, K.O. Kortanek, J.A. Kaliski, and S. Huang, \u201cNear-boundary behavior of primal-dual potential reduction algorithms for linear programming,\u201dMathematical Programming 58 (1993) 243\u2013255.","journal-title":"Mathematical Programming"},{"key":"BF02614377_CR49","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1287\/moor.19.1.53","volume":"19","author":"Y. Ye","year":"1994","unstructured":"Y. Ye, M.J. Todd, and S. Mizuno, \u201cAn $$O(\\sqrt n L)$$ -iteration homogencous and self-dual linear programming algorithm,\u201dMathematics of Operations Research 19 (1994) 53\u201367.","journal-title":"Mathematics of Operations Research"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02614377.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02614377\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02614377","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T08:49:24Z","timestamp":1558342164000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02614377"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,1]]}},"alternative-id":["BF02614377"],"URL":"https:\/\/doi.org\/10.1007\/bf02614377","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,1]]}}}