{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T18:56:13Z","timestamp":1772045773617,"version":"3.50.1"},"reference-count":116,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1993,3,1]],"date-time":"1993-03-01T00:00:00Z","timestamp":730944000000},"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":[[1993,3]]},"DOI":"10.1007\/bf02096259","type":"journal-article","created":{"date-parts":[[2005,9,12]],"date-time":"2005-09-12T18:23:22Z","timestamp":1126549402000},"page":"107-138","source":"Crossref","is-referenced-by-count":35,"title":["Degeneracy in interior point methods for linear programming: a survey"],"prefix":"10.1007","volume":"46-47","author":[{"given":"O.","family":"G\u00fcler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"den Hertog","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Roos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T.","family":"Terlaky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T.","family":"Tsuchiya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02096259_CR1","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/BF01587095","volume":"44","author":"I. Adler","year":"1989","unstructured":"I. Adler, N. Karmarkar, M.G.C. Resende and G. Veiga, An implementation of Karmarkar's algorithm for linear programming, Math. Progr. 44 (1989) 297\u2013335. Errata in: Math. Progr. 50 (1991) 415.","journal-title":"Math. Progr."},{"key":"BF02096259_CR2","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF01758841","volume":"8","author":"I. Adler","year":"1992","unstructured":"I. Adler and D.D.C. Monteiro, A geometric view of parametric linear programming, Algorithmica 8 (1992) 161\u2013176.","journal-title":"Algorithmica"},{"key":"BF02096259_CR3","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01594923","volume":"50","author":"I. Adler","year":"1991","unstructured":"I. Adler and D.D.C. Monteiro, Limiting behavior of the affine scaling continuous trajectories for linear programming problems, Math. Progr. 50 (1991) 29\u201351.","journal-title":"Math. Progr."},{"key":"BF02096259_CR4","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/BF01580774","volume":"41","author":"K.M. Anstreicher","year":"1988","unstructured":"K.M. Anstreicher, Linear programming and the Newton barrier flow, Math. Progr. 41 (1988) 363\u2013373.","journal-title":"Math. Progr."},{"key":"BF02096259_CR5","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF01585736","volume":"46","author":"M.D. Asic","year":"1990","unstructured":"M.D. Asic, V.V. Kovacevic-Vujcic and M.D. Radosavljevic-Nikolic, Asymptotic behavior of Karmarkar's method for linear programming, Math. Progr. 46 (1990) 173\u2013190.","journal-title":"Math. Progr."},{"key":"BF02096259_CR6","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1090\/conm\/114\/1097872","volume":"114","author":"M.D. Asic","year":"1990","unstructured":"M.D. Asic, V.V. Kovacevic-Vujcic and M.D. Radosavljevic-Nikolic, A note on limiting behavior of the projective and the affine rescaling algorithms, Contemp. Math. 114 (1990) 151\u2013157.","journal-title":"Contemp. Math."},{"key":"BF02096259_CR7","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1137\/1011060","volume":"11","author":"M.L. Balinski","year":"1969","unstructured":"M.L. Balinski and A.W. Tucker, Duality theory of linear programs: A constructive approach with applications, SIAM Rev. 11 (1969) 499\u2013581.","journal-title":"SIAM Rev."},{"key":"BF02096259_CR8","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/BF02592024","volume":"36","author":"E.R. Barnes","year":"1986","unstructured":"E.R. Barnes, A variation on Karmarkar's algorithm for solving linear programming problems, Math. Progr. 36 (1986) 174\u2013182.","journal-title":"Math. Progr."},{"key":"BF02096259_CR9","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1090\/conm\/114\/1097870","volume":"114","author":"E.R. Barnes","year":"1990","unstructured":"E.R. Barnes, Some results concerning convergence of the affine scaling algorithm, Contemp. Math. 114 (1990) 131\u2013139.","journal-title":"Contemp. Math."},{"key":"BF02096259_CR10","series-title":"Working Paper","volume-title":"A polynomial-time version of the affine scaling algorithm","author":"E.R. Barnes","year":"1988","unstructured":"E.R. Barnes, S. Chopra and D.L. Jensen, A polynomial-time version of the affine scaling algorithm, Working Paper 88-101, Graduate School of Business and Administration, New York University, NY (1988)."},{"key":"BF02096259_CR11","first-page":"499","volume":"314","author":"D.A. Bayer","year":"1989","unstructured":"D.A. Bayer and J.C. Lagarias, The nonlinear geometry of linear programming, I. Affine and projective scaling trajectories, II. Legendre transform coordinates, Trans. AMS 314 (1989) 499\u2013581.","journal-title":"Trans. AMS"},{"key":"BF02096259_CR12","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1287\/opre.40.5.885","volume":"40","author":"R.E. Bixby","year":"1992","unstructured":"R.E. Bixby, J.W. Gregory, I.J. Lustig, R.E. Marsten and D.F. Shanno, Very large-scale linear programming: A case study in combining interior point and simplex methods, Oper. Res. 40 (1992) 885\u2013897.","journal-title":"Oper. Res."},{"key":"BF02096259_CR13","series-title":"Technical Report","volume-title":"Recovering an optimal LP basis from an interior point solution","author":"R.E. Bixby","year":"1992","unstructured":"R.E. Bixby and M.J. Saltzman, Recovering an optimal LP basis from an interior point solution, Technical Report 607, Department of Mathematical Sciences, Clemson University, Clemson, SC (1992)."},{"key":"BF02096259_CR14","series-title":"Research Memorandum","volume-title":"A class of algorithms for linear programming","author":"V. Chandru","year":"1985","unstructured":"V. Chandru and B. Kochar, A class of algorithms for linear programming, Research Memorandum 85-14, Department of Industrial Engineering, Purdue University, West Lafayette, IN (1985)."},{"key":"BF02096259_CR15","series-title":"Memorandum","volume-title":"An opposite sign algorithm for purification to an extreme point solution","author":"A. Charnes","year":"1963","unstructured":"A. Charnes and K.O. Kortanek, An opposite sign algorithm for purification to an extreme point solution, Memorandum No. 129, Office of Naval Research, Northwestern University, Evanston, IL (1963)."},{"key":"BF02096259_CR16","volume-title":"Linear Programming and Extensions","author":"G.B. Dantzig","year":"1963","unstructured":"G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963)."},{"key":"BF02096259_CR17","first-page":"674","volume":"8","author":"I.I. Dikin","year":"1967","unstructured":"I.I. Dikin, Iterative solution of problems of linear and quadratic programming, Sov. Math. Doklady 8 (1967) 674\u2013675.","journal-title":"Sov. Math. Doklady"},{"key":"BF02096259_CR18","first-page":"54","volume":"12","author":"I.I. Dikin","year":"1974","unstructured":"I.I. Dikin, On the speed of an iterative process, Upravlyaemye Sistemi 12 (1974) 54\u201360.","journal-title":"Upravlyaemye Sistemi"},{"key":"BF02096259_CR19","doi-asserted-by":"crossref","unstructured":"I.I. Dikin, Determination of the interior point of a system of linear inequalities, Cybern. Syst. Anal. 1 (1992).","DOI":"10.1007\/BF01125128"},{"key":"BF02096259_CR20","series-title":"Technical Report","volume-title":"On the convergence of dual variables","author":"I.I. Dikin","year":"1991","unstructured":"I.I. Dikin, On the convergence of dual variables, Technical Report, Siberian Energy Institute, Irkutsk, USSR (1991)."},{"key":"BF02096259_CR21","series-title":"Technical Report","volume-title":"A study of indicators for identifying zero variables in interior point methods","author":"A.S. El-Bakry","year":"1991","unstructured":"A.S. El-Bakry, R.A. Tapia and Y. Zhang, A study of indicators for identifying zero variables in interior point methods, Technical Report 91-15, Department of Mathematical Sciences, Rice University, Houston, TX (1991)."},{"key":"BF02096259_CR22","unstructured":"T. Gal,Postoptimal Analysis, Parametric Programming and Related Topics (McGraw-Hill, 1979)."},{"key":"BF02096259_CR23","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01719736","volume":"8","author":"T. Gal","year":"1986","unstructured":"T. Gal, Shadow prices and sensitivity analysis in linear programming under degeneracy, state-of-the-art-survey, OR Spektrum 8 (1986) 59\u201371.","journal-title":"OR Spektrum"},{"key":"BF02096259_CR24","first-page":"17","volume":"47","author":"D.M. Gay","year":"1991","unstructured":"D.M. Gay, Stopping tests that compute optimal solutions for interior-point linear programming algorithms, in:Advances in Numberical Partial Differential Equations and Optimization, Proc. 5th Mexico-United States Workshop, eds. S. Gomez, J.P. Hennart and R.A. Tapia, Proc. in Applied Mathematics, Vol. 47 (1991) pp. 17\u201342.","journal-title":"Advances in Numberical Partial Differential Equations and Optimization"},{"key":"BF02096259_CR25","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02591685","volume":"37","author":"D.M. Gay","year":"1987","unstructured":"D.M. Gay, A variant of Karmarkar's linear programming problems in standard form, Math. Progr. 37 (1987) 81\u201390. Errata in: Math. Progr. 40 (1988) 111.","journal-title":"Math. Progr."},{"key":"BF02096259_CR26","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/BF02592025","volume":"36","author":"P.E. Gill","year":"1986","unstructured":"P.E. Gill, W. Murray, M.A. Saunders, J.A. Tomlin and M.H. Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method, Math. Progr. 36 (1986) 183\u2013209.","journal-title":"Math. Progr."},{"key":"BF02096259_CR27","first-page":"141","volume-title":"Optimization, Handbooks in Operations Research and Management Science, Vol. 1","author":"D. Goldfarb","year":"1989","unstructured":"D. Goldfarb and M.J. Todd, Linear programming, in:Optimization, Handbooks in Operations Research and Management Science, Vol. 1, eds. G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd (North-Holland, Amsterdam, The Netherlands, 1989) pp. 141\u2013170."},{"key":"BF02096259_CR28","volume-title":"Linear Inequalities and Related Systems","author":"A.J. Goldman","year":"1956","unstructured":"A.J. Goldman and A.W. Tucker, Theory of linear programming, in:Linear Inequalities and Related Systems, eds. H.W. Kuhn and A.W. Tucker, Annals of Mathematical Studies 38 (Princeton University Press, Princeton, NJ, 1956)."},{"key":"BF02096259_CR29","first-page":"1","volume-title":"Progress in Mathematical Programming: Interior Point and Related Methods","author":"C.C. Gonzaga","year":"1989","unstructured":"C.C. Gonzaga, An algorithm for solving linear programming problems inO(n 3 L) operations, in:Progress in Mathematical Programming: Interior Point and Related Methods, ed. N. Megiddo (Springer, New York, 1989) pp. 1\u201328."},{"key":"BF02096259_CR30","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF01588776","volume":"49","author":"C.C. Gonzaga","year":"1990","unstructured":"C.C. Gonzaga, Polynomial affine algorithms for linear programming, Math. Progr. 49 (1990) 7\u201321.","journal-title":"Math. Progr."},{"key":"BF02096259_CR31","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1137\/0801018","volume":"1","author":"C.C. Gonzaga","year":"1991","unstructured":"C.C. Gonzaga, Large step path-following methods for linear programming, part I: Barrier function method, SIAM J. Optim. 1 (1991) 268\u2013279.","journal-title":"SIAM J. Optim."},{"key":"BF02096259_CR32","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1137\/0801019","volume":"1","author":"C.C. Gonzaga","year":"1991","unstructured":"C.C. Gonzaga, Large step path-following methods for linear programming, part II: Potential reduction method, SIAM J. Optim. 1 (1991) 280\u2013292.","journal-title":"SIAM J. Optim."},{"key":"BF02096259_CR33","series-title":"Technical Report","volume-title":"Convergence of the large step primal affine scaling algorithm for primal nondegenerate linear programs","author":"C.C. Gonzaga","year":"1990","unstructured":"C.C. Gonzaga, Convergence of the large step primal affine scaling algorithm for primal nondegenerate linear programs, Technical Report ES-230\/90, Department of Systems Engineering and Computer Sciences, COPPE Federal University of Rio de Janeiro, Rio de Janeiro, Brazil (1990)."},{"key":"BF02096259_CR34","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01759039","volume":"6","author":"C.C. Gonzaga","year":"1991","unstructured":"C.C. Gonzaga, Search directions for interior linear programming methods, Algorithmica 6 (1991) 153\u2013181.","journal-title":"Algorithmica"},{"key":"BF02096259_CR35","series-title":"Technical Report","volume-title":"A simple presentation of Karmarkar's algorithm","author":"C.C. Gonzaga","year":"1988","unstructured":"C.C. Gonzaga, A simple presentation of Karmarkar's algorithm, Technical Report, Department of Systems Engineering and Computer Sciences, COPPE Federal University of Rio de Janeiro, Rio de Janeiro, Brazil (1988)."},{"key":"BF02096259_CR36","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 programminig, SIAM Rev. 34 (1992) 167\u2013227.","journal-title":"SIAM Rev."},{"key":"BF02096259_CR37","series-title":"Working Paper","volume-title":"Existence of interior points and interior paths in nonlinear monotone complementarity problems","author":"O. G\u00fcler","year":"1990","unstructured":"O. G\u00fcler, Existence of interior points and interior paths in nonlinear monotone complementarity problems, Working Paper, The College of Business Administration, The University of Iowa, Iowa City, Iowa (1990), to appear in: Math. Oper. Res."},{"key":"BF02096259_CR38","series-title":"Working Paper","volume-title":"Convergence behavior of some interior-point algorithms","author":"O. G\u00fcler","year":"1991","unstructured":"O. G\u00fcler and Y. Ye, Convergence behavior of some interior-point algorithms, Working Paper 91-04, The College of Business Administration, The University of Iowa, Iowa City, Iowa (1991), to appear in: Math. Progr."},{"key":"BF02096259_CR39","series-title":"Technical Report","volume-title":"Interior point approach to the theory of linear programming","author":"O. G\u00fcler","year":"1992","unstructured":"O. G\u00fcler, C. Roos, T. Terlaky and J.-Ph. Vial, Interior point approach to the theory of linear programming, Technical Report No. 1992.3, D\u00e9partement d'Economie Commerciale et Industrielle, Universit\u00e9 de Gen\u00e8ve, Switzerland (1992)."},{"key":"BF02096259_CR40","unstructured":"Hall and R.J. Vanderbei, private communication (1992)."},{"key":"BF02096259_CR41","volume-title":"Interior point approach to linear, quadratic and convex programming \u2014 Algorithms and complexity","author":"D. Hertog den","year":"1992","unstructured":"D. den Hertog, Interior point approach to linear, quadratic and convex programming \u2014 Algorithms and complexity, Ph.D. Thesis, Faculty of Mathematics and Informatics, TU Delft, Delft, The Netherlands (1992) (Kluwer, Dordrecht, The Netherlands), to be published."},{"key":"BF02096259_CR42","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1007\/BF01582902","volume":"52","author":"D. Hertog den","year":"1991","unstructured":"D. den Hertog and C. Roos, Survey of search directions of interior point methods, Math. Progr. 52 (1991) 481\u2013509.","journal-title":"Math. Progr."},{"key":"BF02096259_CR43","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0024-3795(91)90266-Y","volume":"152","author":"D. Hertog den","year":"1991","unstructured":"D. den Hertog, C. Roos and T. Terlaky, A potential-reduction variant of Renegar's short-step path-following method for linear programming, Lin. Alg. Appl. 152 (1991) 43\u201368.","journal-title":"Lin. Alg. Appl."},{"key":"BF02096259_CR44","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1137\/0802006","volume":"2","author":"D. Hertog den","year":"1992","unstructured":"D. den Hertog, C. Roos and J.-Ph. Vial, A complexity reduction for the long-step path-following algorithm for linear programming, SIAM J. Optim. 2 (1992) 71\u201387.","journal-title":"SIAM J. Optim."},{"key":"BF02096259_CR45","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01580721","volume":"40","author":"H. Imai","year":"1988","unstructured":"H. Imai, On the convexity of the multiplicative version of Karmarkar's potential function, Math. Progr. 40 (1988) 29\u201332.","journal-title":"Math. Progr."},{"key":"BF02096259_CR46","series-title":"Technical Report","volume-title":"A proof of the polynomiality of the Iri-Imai method for linear programming","author":"M. Iri","year":"1991","unstructured":"M. Iri, A proof of the polynomiality of the Iri-Imai method for linear programming, Technical Report, Department of Mathematical Engineering and Information Physics, The University of Tokyo, Tokyo, Japan (1991)."},{"key":"BF02096259_CR47","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/BF01840457","volume":"1","author":"M. Iri","year":"1986","unstructured":"M. Iri and H. Imai, A multiplicative barrier function method for linear programming, Algorithmica 1 (1986) 455\u2013482.","journal-title":"Algorithmica"},{"key":"BF02096259_CR48","series-title":"Technical Report","volume-title":"An interior point approach to postoptimal and parametric analysis in linear programming","author":"B. Jansen","year":"1992","unstructured":"B. Jansen, C. Roos and T. Terlaky, An interior point approach to postoptimal and parametric analysis in linear programming, Technical Report No. 92-21, Faculty of Mathematics and Informatics, TU Delft, Delft, The Netherlands (1992), to appear in Math. Progr."},{"key":"BF02096259_CR49","volume-title":"A decomposition variant for large scale linear programming","author":"J.A. Kaliski","year":"1992","unstructured":"J.A. Kaliski, A decomposition variant for large scale linear programming, Ph.D. Thesis, Department of Management Sciences, The University of Iowa, Iowa City, Iowa (1992)."},{"key":"BF02096259_CR50","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984) 373\u2013395.","journal-title":"Combinatorica"},{"key":"BF02096259_CR51","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1007\/BF01840459","volume":"1","author":"M. Kojima","year":"1986","unstructured":"M. Kojima, Determining basic variables of optimal solutions in Karmarkar's new LP algorithm, Algorithmica 1 (1986) 499\u2013515.","journal-title":"Algorithmica"},{"key":"BF02096259_CR52","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01581234","volume":"59","author":"M. Kojima","year":"1993","unstructured":"M. Kojima, N. Megiddo and S. Mizuno, Theoretical convergence of large-step primal-dual interior point algorithms for linear programs, Math. Progr. 59 (1993) 1\u201322.","journal-title":"Math. Progr."},{"key":"BF02096259_CR53","doi-asserted-by":"crossref","first-page":"662","DOI":"10.1287\/moor.15.4.662","volume":"15","author":"M. Kojima","year":"1990","unstructured":"M. Kojima, S. Mizuno and T. Noma, Limiting behavior of trajectories generated by a continuation method for monotone complementarity problems, Math. Oper. Res. 15 (1990) 662\u2013675.","journal-title":"Math. Oper. Res."},{"key":"BF02096259_CR54","first-page":"41","volume":"4","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. 4 (1989) 41\u201326.","journal-title":"Math. Progr."},{"key":"BF02096259_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-54509-3","volume-title":"A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems","author":"M. Kojima","year":"1991","unstructured":"M. Kojima, N. Megiddo, T. Noma and A. Yoshise,A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science 538 (Springer, New York, 1991)."},{"key":"BF02096259_CR56","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, Math. Progr. 50 (1991) 331\u2013342.","journal-title":"Math. Progr."},{"key":"BF02096259_CR57","series-title":"Research Report on Information Sciences","first-page":"152","volume-title":"An efficient implementation of Karmarkar's new LP algorithm","author":"M. Kojima","year":"1986","unstructured":"M. Kojima and K. Tone, An efficient implementation of Karmarkar's new LP algorithm, Research Report on Information Sciences B-180, Department of Information Sciences, Tokyo Institute of Technology, Tokyo 152, Japan (1986)."},{"key":"BF02096259_CR58","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1002\/1520-6750(198808)35:4<571::AID-NAV3220350410>3.0.CO;2-L","volume":"35","author":"K.O. Kortanek","year":"1988","unstructured":"K.O. Kortanek and J. Zhu, New purification algorithms for linear programming, Naval Res. Log. Quarterly 35 (1988) 571\u2013583.","journal-title":"Naval Res. Log. Quarterly"},{"key":"BF02096259_CR59","volume-title":"Interior point methods for mathematical programming: A bibliography, Diskussionsbeitrag Nr. 171","author":"E. Kranich","year":"1991","unstructured":"E. Kranich, Interior point methods for mathematical programming: A bibliography, Diskussionsbeitrag Nr. 171, Gesamthochschule FernUniversit\u00e4t Hagen, Germany (1991). Can be obtained by e-mail: netlib@research.att.com."},{"key":"BF02096259_CR60","volume-title":"An implementation of a strongly polynomial time algorithm for basis recovery (using an interior point method), Technical Report (in preparation)","author":"I.J. Lustig","year":"1992","unstructured":"I.J. Lustig, An implementation of a strongly polynomial time algorithm for basis recovery (using an interior point method), Technical Report (in preparation), School of Engineering and Applied Science, Department of Civil Engineering and Operations Research, Princeton University, Princeton, NJ (1992)."},{"key":"BF02096259_CR61","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1137\/0802022","volume":"2","author":"I.J. Lustig","year":"1990","unstructured":"I.J. Lustig, R.E. Marsten and D.F. Shanno, On implementing Mehrotra's predictor corrector interior point method for linear programming, SIAM J. Optim. 2 (1990) 435\u2013449.","journal-title":"SIAM J. Optim."},{"key":"BF02096259_CR62","first-page":"41","volume":"19","author":"I.J. Lustig","year":"1991","unstructured":"I.J. Lustig, R.E. Marsten and D.F. Shanno, Interior method vs. simplex method: Beyond netlib, COAL Newsletter 19 (1991) 41\u201344.","journal-title":"COAL Newsletter"},{"key":"BF02096259_CR63","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1287\/ijoc.1.4.287","volume":"1","author":"R.E. Marsten","year":"1991","unstructured":"R.E. Marsten, M.J. Saltzman, D.F. Shanno, J.F. Ballintijn and G.S. Pierce, Implementation of a dual affine interior point algorithm for linear programming, ORSA J. Comput. 1 (1991) 287\u2013297.","journal-title":"ORSA J. Comput."},{"key":"BF02096259_CR64","doi-asserted-by":"crossref","first-page":"101","DOI":"10.2140\/pjm.1980.88.101","volume":"88","author":"L. McLinden","year":"1980","unstructured":"L. McLinden, An analogue of Moreau's proximation theorem, with application to the nonlinear complementarity problem, Pacific J. Math. 88 (1980) 101\u2013161.","journal-title":"Pacific J. Math."},{"key":"BF02096259_CR65","first-page":"251","volume-title":"Variational Inequalities and Complementarity Problems","author":"L. McLinden","year":"1980","unstructured":"L. McLinden, The complementarity problem for maximal monotone multifunctions, in:Variational Inequalities and Complementarity Problems, eds. R.W. Cottle, F. Giannessi and J.L. Lions (Wiley, New York, 1980) pp. 251\u2013270."},{"key":"BF02096259_CR66","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/978-1-4613-9617-8_8","volume-title":"Progress in Mathematical Programming: Interior and Related Methods","author":"N. Megiddo","year":"1989","unstructured":"N. Megiddo, Pathways to the optimal set in linear programming, in:Progress in Mathematical Programming: Interior and Related Methods, ed. N. Megiddo (Springer, New York, 1989) pp. 131\u2013158."},{"key":"BF02096259_CR67","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1287\/ijoc.3.1.63","volume":"3","author":"N. Megiddo","year":"1991","unstructured":"N. Megiddo, On finding primal- and dual-optimal bases, ORSA J. Comput. 3 (1991) 63\u201365.","journal-title":"ORSA J. Comput."},{"key":"BF02096259_CR68","series-title":"Technical Report RJ","volume-title":"Switching from a primal-dual Newton algorithm to a primal-dual (interior) simplex-algorithm","author":"N. Megiddo","year":"1988","unstructured":"N. Megiddo, Switching from a primal-dual Newton algorithm to a primal-dual (interior) simplex-algorithm, Technical Report RJ 6327, IBM Almaden Research Center, San Jose, CA (1988)."},{"key":"BF02096259_CR69","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1287\/moor.14.1.97","volume":"14","author":"N. Megiddo","year":"1987","unstructured":"N. Megiddo and M. Shub, Boundary behavior of interior point algorithms in linear programming, Math. Oper. Res. 14 (1987) 97\u2013114.","journal-title":"Math. Oper. Res."},{"key":"BF02096259_CR70","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0024-3795(91)90277-4","volume":"152","author":"S. Mehrotra","year":"1991","unstructured":"S. Mehrotra, On finding a vertex solution using interior point methods, Lin. Alg. Appl. 152 (1991) 233\u2013253.","journal-title":"Lin. Alg. Appl."},{"key":"BF02096259_CR71","series-title":"Technical Report","volume-title":"Finite termination and superlinear convergence in primal-dual methods","author":"S. Mehrotra","year":"1991","unstructured":"S. Mehrotra, Finite termination and superlinear convergence in primal-dual methods, Technical Report 91-13, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL (1991)."},{"key":"BF02096259_CR72","series-title":"Technical Report","volume-title":"Quadratic convergence in a primal-dual method","author":"S. Mehrotra","year":"1991","unstructured":"S. Mehrotra, Quadratic convergence in a primal-dual method, Technical Report 91-15, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL (1991)."},{"key":"BF02096259_CR73","series-title":"Technical Report","volume-title":"On finding the optimal face of linear programs","author":"S. Mehrotra","year":"1991","unstructured":"S. Mehrotra and Y. Ye, On finding the optimal face of linear programs, Technical Report 91-10, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL (1991)."},{"key":"BF02096259_CR74","series-title":"Technical Report","volume-title":"On adaptive-step primal-dual interior-point algorithms for linear programming","author":"S. Mizuno","year":"1991","unstructured":"S. Mizuno, M.J. Todd and Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Technical Report No. 944, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY (1991), to appear in: Math. Oper. Res."},{"key":"BF02096259_CR75","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1287\/moor.17.1.225","volume":"17","author":"D.D.C. Monteiro","year":"1992","unstructured":"D.D.C. Monteiro, On the continuous trajectories for a potential reduction algorithm for linear programming, Math. Oper. Res. 17 (1992) 225\u2013253.","journal-title":"Math. Oper. Res."},{"key":"BF02096259_CR76","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1090\/conm\/114\/1097875","volume":"114","author":"D.D.C. Monteiro","year":"1991","unstructured":"D.D.C. Monteiro, Convergence and boundary behavior of the projective scaling trajectories for linear programming, Contemp. Math. 114 (1991) 213\u2013232.","journal-title":"Contemp. Math."},{"key":"BF02096259_CR77","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/BF01587075","volume":"44","author":"D.D.C. Monteiro","year":"1989","unstructured":"D.D.C. Monteiro and I. Adler, Interior path-following primal-dual algorithms, Part I: Linear programming, Math. Progr. 44 (1989) 27\u201341.","journal-title":"Math. Progr."},{"key":"BF02096259_CR78","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1287\/moor.15.2.191","volume":"15","author":"D.D.C. Monteiro","year":"1990","unstructured":"D.D.C. Monteiro, I. Adler and M.G.C. Resende, A polynomial-time primal-dual affine scaling algorithms for linear and convex quadratic programming and its power series extension, Math. Oper. Res. 15 (1990) 191\u2013214.","journal-title":"Math. Oper. Res."},{"key":"BF02096259_CR79","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's method, for linear programming, Math. Progr. 40 (1988) 59\u201393.","journal-title":"Math. Progr."},{"key":"BF02096259_CR80","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF01586056","volume":"54","author":"C. Roos","year":"1992","unstructured":"C. Roos and J.-Ph. Vial, A polynomial method of approximate centers for linear programming, Math. Progr. 54 (1992) 295\u2013305.","journal-title":"Math. Progr."},{"key":"BF02096259_CR81","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1986","unstructured":"A. Schrijver,Theory of Linear and Integer Programming (Wiley, New York, 1986)."},{"key":"BF02096259_CR82","unstructured":"D.F. Shanno, private communication (1991)."},{"key":"BF02096259_CR83","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1002\/1520-6750(198808)35:4<473::AID-NAV3220350403>3.0.CO;2-C","volume":"35","author":"H.D. Sherali","year":"1988","unstructured":"H.D. Sherali, B.O. Skarpness and B. Kim, An assumption-free analysis of the scaling algorithm for linear programs, with application to theL 1 estimation problem, Naval Res. Log. Quarterly 35 (1988) 473\u2013492.","journal-title":"Naval Res. Log. Quarterly"},{"key":"BF02096259_CR84","first-page":"866","volume-title":"Lecture Notes in Control and Information Sciences, vol. 84","author":"G. Sonnevend","year":"1985","unstructured":"Gy. Sonnevend, An \u201canalytic center\u201d for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, in:Lecture Notes in Control and Information Sciences, vol. 84, eds. A. Pr\u00e9kopa, J. Szelezs\u00e1n and B. Straziczki (Springer, New York, 1985) pp. 866\u2013876."},{"key":"BF02096259_CR85","first-page":"197","volume-title":"Proc. 13th IFIP Conf.","author":"K. Tanabe","year":"1988","unstructured":"K. Tanabe, Centered Newton method for mathematical programming, in:Proc. 13th IFIP Conf., eds. M. Iri and K. Yajima (Springer, Berlin, 1988) pp. 197\u2013206."},{"key":"BF02096259_CR86","first-page":"119","volume":"38","author":"K. Tanabe","year":"1990","unstructured":"K. Tanabe, Centered Newton method for nonlinear programming (in Japanese), in: Proc. Inst. Statist. Math. 38 (Tokyo, 1990) 119\u2013120.","journal-title":"Proc. Inst. Statist. Math."},{"key":"BF02096259_CR87","first-page":"132","volume-title":"Proc. Annual Meeting of the Operations Research Society of Japan","author":"K. Tanabe","year":"1987","unstructured":"K. Tanabe and T. Tsuchiya, Global analysis of dynamical systems associated with Karmarkar's method for linear programming, in:Proc. Annual Meeting of the Operations Research Society of Japan, Chigasaki, Japan (1987) pp. 132\u2013133."},{"key":"BF02096259_CR88","series-title":"Technical Report","volume-title":"A fast optimal basis identification technique for interior point linear programming methods","author":"R. A. Tapia","year":"1989","unstructured":"R. A. Tapia and Y. Zhang, A fast optimal basis identification technique for interior point linear programming methods, Technical Report 89-1, Department of Mathematical Sciences, Rice University, Houston, TX (1989)."},{"key":"BF02096259_CR89","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0024-3795(91)90281-Z","volume":"152","author":"R.A. Tapia","year":"1991","unstructured":"R.A. Tapia and Y. Zhang, An optimal basis identification technique for interior point linear programming algorithms, Lin. Alg. Appl. 152 (1991) 343\u2013363.","journal-title":"Lin. Alg. Appl."},{"key":"BF02096259_CR90","doi-asserted-by":"crossref","unstructured":"T. Terlaky and S. Zhang, A survey of pivot rules for linear programming, Ann. Oper. Res. 46 (1993), this volume.","DOI":"10.1007\/BF02096264"},{"key":"BF02096259_CR91","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1287\/moor.13.4.650","volume":"13","author":"M.J. Todd","year":"1988","unstructured":"M.J. Todd, Improved bounds and containing ellipsoids in Karmarkar's linear programming algorithm, Math. Oper. Res. 13 (1988) 650\u2013659.","journal-title":"Math. Oper. Res."},{"key":"BF02096259_CR92","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. Burrell, An extension of Karmarkar's algorithm for linear programming using dual variables, Algorithmica 1 (1986) 409\u2013424.","journal-title":"Algorithmica"},{"key":"BF02096259_CR93","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, Math. Oper. Res. 15 (1990) 508\u2013529.","journal-title":"Math. Oper. Res."},{"key":"BF02096259_CR94","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/BF01580904","volume":"52","author":"P. Tseng","year":"1992","unstructured":"P. Tseng and Z.Q. Luo, On the convergence of the affine-scaling algorithm, Math. Progr. 52 (1992) 301\u2013319.","journal-title":"Math. Progr."},{"key":"BF02096259_CR95","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1287\/moor.17.3.527","volume":"17","author":"T. Tsuchiya","year":"1992","unstructured":"T. Tsuchiya, Global convergence property of the affine scaling methods for primal degenerate linear programming problems, Math. Oper. Res. 17 (1992) 527\u2013557.","journal-title":"Math. Oper. Res."},{"key":"BF02096259_CR96","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/BF01582896","volume":"52","author":"T. Tsuchiya","year":"1991","unstructured":"T. Tsuchiya, Global convergence of the affine scaling methods for degenerate linear programming problems, Math. Progr. 52 (1991) 377\u2013404.","journal-title":"Math. Progr."},{"key":"BF02096259_CR97","series-title":"Research Memorandum","volume-title":"Quadratic convergence of Iri and Imai's algorithm for degenerate linear programming problems","author":"T. Tsuchiya","year":"1991","unstructured":"T. Tsuchiya, Quadratic convergence of Iri and Imai's algorithm for degenerate linear programming problems, Research Memorandum No. 412, The Institute of Statistical Mathematics, Tokyo, Japan (1991), to appear in: J. Optim. Theory Appl."},{"key":"BF02096259_CR98","volume-title":"A study on global and local convergence of interior point algorithms for linear programming (in Japanese)","author":"T. Tsuchiya","year":"1991","unstructured":"T. Tsuchiya, A study on global and local convergence of interior point algorithms for linear programming (in Japanese), Ph.D. Thesis, Faculty of Engineering, The University of Tokyo, Tokyo, Japan (1991)."},{"key":"BF02096259_CR99","series-title":"Research Memorandum","volume-title":"Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems","author":"T. Tsuchiya","year":"1992","unstructured":"T. Tsuchiya and M. Muramatsu, Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems, Research Memorandum 423, The Institute of Statistical Mathematics, Tokyo, Japan (1992)."},{"key":"BF02096259_CR100","first-page":"22","volume":"33","author":"T. Tsuchiya","year":"1990","unstructured":"T. Tsuchiya and K. Tanabe, Local convergence properties of new methods in linear programming, J. Oper. Res. Soc. Japan 33 (1990) 22\u201345.","journal-title":"J. Oper. Res. Soc. Japan"},{"key":"BF02096259_CR101","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1090\/conm\/114\/1097868","volume":"114","author":"R.J. Vanderbei","year":"1990","unstructured":"R.J. Vanderbei and J.C. Lagarias, Dikin's convergence result for the affine-scaling algorithm, Contemp. Math. 114 (1990) 109\u2013119.","journal-title":"Contemp. Math."},{"key":"BF02096259_CR102","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/BF01840454","volume":"1","author":"R.J. Vanderbei","year":"1986","unstructured":"R.J. Vanderbei, M.S. Meketon and B.A. Freedman, A modification of Karmarkar's linear programming algorithm, Algorithmica 1 (1986) 395\u2013407.","journal-title":"Algorithmica"},{"key":"BF02096259_CR103","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02055188","volume":"27","author":"J.E. Ward","year":"1990","unstructured":"J.E. Ward and R.E. Wendell, Approaches to sensitivity analysis in linear programming, Ann. Oper. Res. 27 (1990) 3\u201338.","journal-title":"Ann. Oper. Res."},{"key":"BF02096259_CR104","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1090\/conm\/114\/1097873","volume":"114","author":"C. Witzgall","year":"1990","unstructured":"C. Witzgall, P.T. Boggs and P.D. Domich, On the convergence behavior of trajectories for linear programming, Contemp. Math. 114 (1990) 161\u2013187.","journal-title":"Contemp. Math."},{"key":"BF02096259_CR105","first-page":"341","volume-title":"Acta Numerica","author":"M.H. Wright","year":"1992","unstructured":"M.H. Wright, Interior point methods for constrained optimization, in:Acta Numerica, ed. A. Iserles (Cambridge University Press, New York, 1992) pp. 341\u2013407."},{"key":"BF02096259_CR106","volume-title":"A polynomially and quadratically convergent method for linear programming, Technical Report","author":"H. Yamashita","year":"1986","unstructured":"H. Yamashita, A polynomially and quadratically convergent method for linear programming, Technical Report, Mathematical Systems Inc., Shinjuku, Tokyo, Japan (1986)."},{"key":"BF02096259_CR107","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0167-6377(87)90016-2","volume":"6","author":"Y. Ye","year":"1987","unstructured":"Y. Ye, Karmarkar's algorithm and the ellipsoid method, Oper. Res. Lett. 6 (1987) 177\u2013182.","journal-title":"Oper. Res. Lett."},{"key":"BF02096259_CR108","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1287\/moor.15.3.564","volume":"15","author":"Y. Ye","year":"1990","unstructured":"Y. Ye, Recovering optimal basis in Karmarkar's polynomial algorithm for linear programming, Math. Oper. Res. 15 (1990) 564\u2013572.","journal-title":"Math. Oper. Res."},{"key":"BF02096259_CR109","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF01594937","volume":"50","author":"Y. Ye","year":"1991","unstructured":"Y. Ye, AnO(n 3 L) potential reduction algorithm for linear programming, Math. Progr. 50 (1991) 239\u2013258.","journal-title":"Math. Progr."},{"key":"BF02096259_CR110","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF01581087","volume":"57","author":"Y. Ye","year":"1992","unstructured":"Y. Ye, On the finite convergence of interior-point algorithms for linear programming, Math. Progr. Ser. B 57 (1992) 325\u2013335.","journal-title":"Math. Progr. Ser. B"},{"key":"BF02096259_CR111","series-title":"Technical Report","doi-asserted-by":"crossref","DOI":"10.21236\/ADA455490","volume-title":"A quadratically convergentO(\u221anL)-iteration algorithm for linear programming","author":"Y. Ye","year":"1991","unstructured":"Y. Ye, O. G\u00fcler, R.A. Tapia and Y. Zhang, A quadratically convergentO(\u221anL)-iteration algorithm for linear programming, Technical Report 91-26, Department of Mathematical Sciences, Rice University, Houston, TX (1991), to appear in: Math. Progr."},{"key":"BF02096259_CR112","unstructured":"Y. Ye and J. Kaliski, private communication (1991)."},{"key":"BF02096259_CR113","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/BF02592079","volume":"39","author":"Y. Ye","year":"1987","unstructured":"Y. Ye and M. Kojima, Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming, Math. Progr. 39 (1987) 305\u2013317.","journal-title":"Math. Progr."},{"key":"BF02096259_CR114","series-title":"Technical Report","doi-asserted-by":"crossref","DOI":"10.21236\/ADA452256","volume-title":"A superlinearly convergentO(\u221anL)-iteration algorithm for linear programming","author":"Y. Ye","year":"1991","unstructured":"Y. Ye, R.A. Tapia and Y. Zhang, A superlinearly convergentO(\u221anL)-iteration algorithm for linear programming, Technical Report 91-22, Department of Mathematical Sciences, Rice University, Houston, TX (1991)."},{"key":"BF02096259_CR115","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01580848","volume":"47","author":"Y. Ye","year":"1990","unstructured":"Y. Ye and M.J. Todd, Containing and shrinking ellipsoids in the path-following algorithm, Math. Progr. 47 (1990) 1\u201310.","journal-title":"Math. Progr."},{"key":"BF02096259_CR116","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1137\/0802015","volume":"2","author":"Y. Zhang","year":"1990","unstructured":"Y. Zhang, R. Tapia and J.E. Dennis, On the superlinear and quadratic convergence of primal-dual interior-point linear programming algorithms, SIAM J. Optim. 2 (1990) 304\u2013324.","journal-title":"SIAM J. Optim."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02096259.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02096259\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02096259","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T11:06:09Z","timestamp":1586430369000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02096259"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,3]]},"references-count":116,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1993,3]]}},"alternative-id":["BF02096259"],"URL":"https:\/\/doi.org\/10.1007\/bf02096259","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,3]]}}}