{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:47:33Z","timestamp":1781077653955,"version":"3.54.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1996,12,1]],"date-time":"1996-12-01T00:00:00Z","timestamp":849398400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[1996,12]]},"DOI":"10.1007\/bf02206818","type":"journal-article","created":{"date-parts":[[2005,10,6]],"date-time":"2005-10-06T00:32:15Z","timestamp":1128558735000},"page":"233-252","source":"Crossref","is-referenced-by-count":15,"title":["A lower bound on the number of iterations of long-step primal-dual linear programming algorithms"],"prefix":"10.1007","volume":"62","author":[{"given":"Michael J.","family":"Todd","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yinyu","family":"Ye","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF02206818_CR1","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1137\/0801003","volume":"1","author":"K.M. Anstreicher","year":"1991","unstructured":"K.M. Anstreicher, On the performance of Karmarkar's algorithm over a sequence of iterations, SIAM J. Optim. 1(1991)22.","journal-title":"SIAM J. Optim."},{"key":"BF02206818_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/9789814354363_0001","volume-title":"Complexity in Numerical Optimization","author":"K.M. Anstreicher","year":"1993","unstructured":"K.M. Anstreicher, J. Ji, F. Potra and Y. Ye, Average performance of a self-dual interior-point algorithm for linear programming, in:Complexity in Numerical Optimization, ed. P. Pardalos (World Scientific, New Jersey, 1993) p. 1."},{"key":"BF02206818_CR3","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, On the worst case complexity of potential reduction algorithms for linear programming, Working Paper 3558-93, Sloan School of Management, MIT, Cambridge, MA 02139, USA (1993)."},{"key":"BF02206818_CR4","first-page":"73","volume-title":"Optimization, Volume 1 ofHandbooks in Operations Research and Management Science","author":"D. Goldfarb","year":"1989","unstructured":"D. Goldfarb and M.J. Todd, Linear programming, in:Optimization, Volume 1 ofHandbooks in Operations Research and Management Science, ed. G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd (North-Holland, Amsterdam, The Netherlands, 1989) p. 73."},{"key":"BF02206818_CR5","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1137\/1034048","volume":"34","author":"C.C. Gonzaga","year":"1992","unstructured":"C.C. Gonzaga, Path following methods for linear programming, SIAM Rev. 34(1992)167.","journal-title":"SIAM Rev."},{"key":"BF02206818_CR6","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1137\/0804028","volume":"4","author":"J. Ji","year":"1994","unstructured":"J. Ji and Y. Ye, A complexity analysis for interior-point algorithms based on Karmarkar's potential function, SIAM J. Optim. 4(1994)512.","journal-title":"SIAM J. Optim."},{"key":"BF02206818_CR7","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N.K. Karmarkar","year":"1984","unstructured":"N.K. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4(1984)373.","journal-title":"Combinatorica"},{"key":"BF02206818_CR8","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF01582151","volume":"61","author":"M. Kojima","year":"1993","unstructured":"M. Kojima, N. Megiddo and S. Mizuno, A primal-dual infeasible-interior-point algorithm for linear programming, Math. Progr. 61(1993)263.","journal-title":"Math. Progr."},{"key":"BF02206818_CR9","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/978-1-4613-9617-8_2","volume-title":"Progress in Mathematical Programming: Interior Point and Related Methods","author":"M. Kojima","year":"1989","unstructured":"M. Kojima, S. Mizuno and A. Yoshise, A primal-dual interior point algorithm for linear programming, in:Progress in Mathematical Programming: Interior Point and Related Methods, ed. N. Megiddo (Springer, New York, 1989) p. 29."},{"key":"BF02206818_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01587074","volume":"44","author":"M. Kojima","year":"1989","unstructured":"M. Kojima, S. Mizuno and A. Yoshise, A polynomial-time algorithm for a class of linear complementarity problems, Math. Progr. 44(1989)1.","journal-title":"Math. Progr."},{"key":"BF02206818_CR11","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, An $$O(\\sqrt {nL} )$$ iteration potential reduction algorithm for linear complementarity problems, Math. Progr. 50(1991)331.","journal-title":"Math. Progr."},{"key":"BF02206818_CR12","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0024-3795(91)90275-2","volume":"152","author":"I.J. Lustig","year":"1991","unstructured":"I.J. Lustig, R.E. Marsten and D.F. Shanno, Computational experience with a primal-dual interior point method for linear programming, Lin. Alg. Appl. 152(1991):191.","journal-title":"Lin. Alg. Appl."},{"key":"BF02206818_CR13","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/BF01581140","volume":"66","author":"I.J. Lustig","year":"1994","unstructured":"I.J. Lustig, R.E. Marsten and D.F. Shanno, Computational experience with a globally convergent primal-dual predictor-corrector algorithm for linear programming, Math. Progr 66(1994)123.","journal-title":"Math. Progr"},{"key":"BF02206818_CR14","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1007\/BF01585180","volume":"62","author":"S. Mehrotra","year":"1993","unstructured":"S. Mehrotra and Y. Ye, On finding an interior point on the optimal face of linear programs, Math. Progr. 62(1993)497.","journal-title":"Math. Progr."},{"key":"BF02206818_CR15","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1287\/moor.18.4.964","volume":"18","author":"S. Mizuno","year":"1993","unstructured":"S. Mizuno, M.J. Todd and Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Math. Oper. Res. 18(1993)964.","journal-title":"Math. Oper. Res."},{"key":"BF02206818_CR16","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/BF01587075","volume":"44","author":"R.D.C. Monteiro","year":"1989","unstructured":"R.D.C. Monteiro and I. Adler, Interior path following primal-dual algorithms: Part I: Linear programming, Math. Progr. 44(1989)27.","journal-title":"Math. Progr."},{"key":"BF02206818_CR17","first-page":"105","volume":"1","author":"A.S. Nemirovsky","year":"1987","unstructured":"A.S. Nemirovsky, An algorithm of the Karmarkar type, Tekhnicheskaya Kibernetika 1(1987)105, translated in: Sov. J. Comp. Syst. Sci. 25(5)(1987)61.","journal-title":"Tekhnicheskaya Kibernetika"},{"key":"BF02206818_CR18","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, On the number of iterations of Karmarkar's algorithm for linear programming, Math. Progr. 62(1993)153.","journal-title":"Math. Progr."},{"key":"BF02206818_CR19","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/BF01582904","volume":"52","author":"G. Sonnevend","year":"1991","unstructured":"G. Sonnevend, J. Stoer and G. Zhao, On the complexity of following the central path of linear programs by linear extrapolation II, Math. Progr. 52(1991)527.","journal-title":"Math. Progr."},{"key":"BF02206818_CR20","first-page":"109","volume-title":"Mathematical Programming: Recent Developments and Applications","author":"M.J. Todd","year":"1989","unstructured":"M.J. Todd, Recent developments and new directions in linear programming, in:Mathematical Programming: Recent Developments and Applications, ed. M. Iri and K. Tanabe (Kluwer Academic, Dordrecht The Netherlands, 1989), p. 109."},{"key":"BF02206818_CR21","first-page":"89","volume-title":"Numerical Analysis 1993, Volume 303 ofPitman Research Notes in Mathematics","author":"M.J. Todd","year":"1994","unstructured":"M.J. Todd, A lower bound on the number of iterations of primal-dual interior-point methods for linear programming, in:Numerical Analysis 1993, Volume 303 ofPitman Research Notes in Mathematics, ed. G.A. Watson and D.F. Griffiths (Longman, Burnt Hill, UK, 1994) p. 89."},{"key":"BF02206818_CR22","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1287\/moor.19.1.38","volume":"19","author":"Y. Ye","year":"1994","unstructured":"Y. Ye, Toward probabilistic analysis of interior-point algorithms for linear programming, Math. Oper. Res. 19(1994)38.","journal-title":"Math. Oper. Res."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02206818.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02206818\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02206818","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T14:35:27Z","timestamp":1557844527000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02206818"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,12]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,12]]}},"alternative-id":["BF02206818"],"URL":"https:\/\/doi.org\/10.1007\/bf02206818","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,12]]}}}