{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T09:39:44Z","timestamp":1648633184411},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1997,5,1]],"date-time":"1997-05-01T00:00:00Z","timestamp":862444800000},"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,5]]},"DOI":"10.1007\/bf02614620","type":"journal-article","created":{"date-parts":[[2007,4,28]],"date-time":"2007-04-28T00:54:01Z","timestamp":1177721641000},"page":"321-333","source":"Crossref","is-referenced-by-count":5,"title":["On the worst case complexity of potential reduction algorithms for linear programming"],"prefix":"10.1007","volume":"77","author":[{"given":"Dimitris","family":"Bertsimas","sequence":"first","affiliation":[]},{"given":"Xiaodong","family":"Luo","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02614620_CR1","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1287\/moor.14.2.294","volume":"14","author":"K.M. Anstreicher","year":"1989","unstructured":"K.M. Anstreicher, The worst-case step in Karmarkar\u2019s algorithm,Mathematics of Operations Research 14 (1989) 295\u2013302.","journal-title":"Mathematics of Operations Research"},{"key":"BF02614620_CR2","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\u2019s algorithm over a sequence of iterations,SIAM Journal on Optimization 1 (1991) 22\u201329.","journal-title":"SIAM Journal on Optimization"},{"key":"BF02614620_CR3","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF01586933","volume":"51","author":"R. Freund","year":"1991","unstructured":"R. Freund, Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function,Mathematical Programming 51 (1991) 203\u2013222.","journal-title":"Mathematical Programming"},{"key":"BF02614620_CR4","first-page":"1","volume-title":"Progress in Mathematical Programming. Interior Point and Related Methods","author":"C.C. Gonzaga","year":"1988","unstructured":"C.C. Gonzaga, An algorithm for solving linear programming problems in O(n 3 L) operations, in: N. Megiddo, ed.,Progress in Mathematical Programming. Interior Point and Related Methods (Springer, New York, 1988) 1\u201328."},{"key":"BF02614620_CR5","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1137\/0802017","volume":"2","author":"C.C. Gonzaga","year":"1992","unstructured":"C.C. Gonzaga and M.J. Todd, An O(\u221anL)-iteration large-step primal-dual affine algorithm for linear programming,SIAM Journal on Optimization 2 (1992) 349\u2013359.","journal-title":"SIAM Journal on Optimization"},{"key":"BF02614620_CR6","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1016\/0167-6377(91)90040-V","volume":"10","author":"J. Kaliski","year":"1991","unstructured":"J. Kaliski and Y. Ye, Convergence behavior of Karmarkar\u2019s projective algorithm for solving a simple linear program,Operations Research Letters 10 (1991) 389\u2013393.","journal-title":"Operations Research Letters"},{"key":"BF02614620_CR7","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1991","unstructured":"N. Karmarkar (1984), A new polynomial-time algorithm for linear programming,Combinatorica 4 (1991) 373\u2013395.","journal-title":"Combinatorica"},{"key":"BF02614620_CR8","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, AnO(\u221anL) iteration potential reduction algorithm for linear complementarity problems,Mathematical Programming 50 (1991) 331\u2013342.","journal-title":"Mathematical Programming"},{"key":"BF02614620_CR9","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/BF01585747","volume":"46","author":"C. McDiarmid","year":"1990","unstructured":"C. McDiarmid, On the improvement per iteration in Karmarkar\u2019s algorithm for linear programming,Mathematical Programming, 46 (1990) 299\u2013320.","journal-title":"Mathematical Programming"},{"key":"BF02614620_CR10","unstructured":"Y. Nesterov, Long-step strategies in interior-point potential reduction methods, Department SES COMIN, Geneva University, 1993."},{"key":"BF02614620_CR11","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\u2019s algorithm for linear programming.Mathematical Programming 62 (1993) 153\u2013197.","journal-title":"Mathematical Programming"},{"key":"BF02614620_CR12","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01580724","volume":"40","author":"J. Renegar","year":"1988","unstructured":"J. Renegar, A polynomial-time algorithm, based on Newton\u2019s method, for linear programming,Mathematical Programming 40 (1988) 59\u201393.","journal-title":"Mathematical Programming"},{"key":"BF02614620_CR13","series-title":"Lecture Notes in Control and Information Sciences","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/BFb0042787","volume-title":"System Modeling and Optimization: Proceedings of the 13th IFIP Conference","author":"K. Tanabe","year":"1988","unstructured":"K. Tanabe, Centered Newton method for mathematical programming, in: M. Iri and K. Yajima, eds.,System Modeling and Optimization: Proceedings of the 13th IFIP Conference, Tokyo, Japan. Aug.\u2013Sept. 1987. Lecture Notes in Control and Information Sciences 113 (Springer, Berlin, 1988) 197\u2013206."},{"key":"BF02614620_CR14","series-title":"Pitman Research Notes in Mathematics","first-page":"237","volume-title":"Numerical Analysis 1993","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: G.A. Watson and D.F. Griffiths, eds.,Numerical Analysis 1993. Pitman Research Notes in Mathematics 303 (Longman Press, Burnt Hill, UK, 1994) 237\u2013259."},{"key":"BF02614620_CR15","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. A centered projective algorithm for linear programming,Mathematics of Operations Research 15 (1990) 508\u2013529.","journal-title":"Mathematics of Operations Research"},{"key":"BF02614620_CR16","unstructured":"M.J. Todd and Y. Ye, A lower bound on the number of iterations of long-step and polynomial interiorpoint programming algorithms, to appear inAnnals of Operations Research (1995)."},{"key":"BF02614620_CR17","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1137\/0219030","volume":"19","author":"Y. Ye","year":"1990","unstructured":"Y. Ye, A class of projective transformations for linear programming,SIAM Journal on Computing 19 (1990) 457\u2013466.","journal-title":"SIAM Journal on Computing"},{"key":"BF02614620_CR18","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF01594937","volume":"50","author":"Y. Ye","year":"1991","unstructured":"Y. Ye, An O(n 3 L) potential reduction algorithm for linear programming.Mathematical Programming 50 (1991) 239\u2013258.","journal-title":"Mathematical Programming"},{"key":"BF02614620_CR19","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF01581269","volume":"58","author":"Y. Ye","year":"1993","unstructured":"Y. Ye, K. Kortanek, J. Kaliski and S. Huang, Near boundary behavior of the primal-dual potential reduction algorithm for linear programming.Mathematical Programming 58 (1993) 243\u2013255.","journal-title":"Mathematical Programming"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02614620.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02614620\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02614620","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T04:49:27Z","timestamp":1558327767000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02614620"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,5]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1997,5]]}},"alternative-id":["BF02614620"],"URL":"https:\/\/doi.org\/10.1007\/bf02614620","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,5]]}}}