{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T17:59:08Z","timestamp":1771005548507,"version":"3.50.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1996,7,1]],"date-time":"1996-07-01T00:00:00Z","timestamp":836179200000},"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":[[1996,7]]},"DOI":"10.1007\/bf02592148","type":"journal-article","created":{"date-parts":[[2007,3,29]],"date-time":"2007-03-29T15:56:37Z","timestamp":1175183797000},"page":"79-120","source":"Crossref","is-referenced-by-count":53,"title":["A primal-dual interior point method whose running time depends only on the constraint matrix"],"prefix":"10.1007","volume":"74","author":[{"given":"Stephen A.","family":"Vavasis","sequence":"first","affiliation":[]},{"given":"Yinyu","family":"Ye","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02592148_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R. K. Ahuja","year":"1993","unstructured":"R. K. Ahuja, T. L. Magnanti and J. B. Orlin,Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Englewood Cliffs, New Jersey, 1993)."},{"key":"BF02592148_CR2","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,Transactions of the AMS 314 (1989) 499\u2013526.","journal-title":"Transactions of the AMS"},{"key":"BF02592148_CR3","first-page":"527","volume":"314","author":"D. A. Bayer","year":"1989","unstructured":"D. A. Bayer and J. C. Lagaria, The nonlinear geometry of linear programming, II. Legendre transform coordinates and central trajectories,Transactions of the AMS 314 (1989) 527\u2013581.","journal-title":"Transactions of the AMS"},{"key":"BF02592148_CR4","first-page":"193","volume":"320","author":"D. A. Bayer","year":"1990","unstructured":"D. A. Bayer and J. C. Lagarias, The nonlinear geometry of linear programming. III. Projective Legendre transform coordinates and Hilbert geometry,Transactions of the AMS 320 (1990) 193\u2013225.","journal-title":"Transactions of the AMS"},{"key":"BF02592148_CR5","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0024-3795(90)90395-S","volume":"139","author":"A. Ben-Tal","year":"1990","unstructured":"A. Ben-Tal and M. Teboulle, A geometric property of the least squares solutions of linear equations,Linear Algebra and Its Applications 139 (1990) 165\u2013170.","journal-title":"Linear Algebra and Its Applications"},{"key":"BF02592148_CR6","first-page":"167","volume-title":"Encyclopedia of Computer Science and Technology","author":"T. Coleman","year":"1993","unstructured":"T. Coleman, Large-scale numerical optimization: introduction and overview, in: A. Kent and J. G. Williams, eds.,Encyclopedia of Computer Science and Technology 28 (Marcel Dekker, New York, 1993) 167\u2013195."},{"key":"BF02592148_CR7","doi-asserted-by":"crossref","first-page":"241","DOI":"10.6028\/jres.071B.033","volume":"71B","author":"J. Edmonds","year":"1967","unstructured":"J. Edmonds, Systems of distinct representatives and linear algebra,Journal of Research of the National Bureau of Standards 71B (1967) 241\u2013245.","journal-title":"Journal of Research of the National Bureau of Standards"},{"key":"BF02592148_CR8","unstructured":"A. Forsgren, On linear least-squares problems with diagnonally dominant weight matrices, Technical Report TRITA-MAT-1995-OS2, Department of Mathematics, Royal Institute of Technology, Stockholm, Sweden."},{"key":"BF02592148_CR9","volume-title":"Matrix Computations","author":"G. H. Golub","year":"1989","unstructured":"G. H. Golub and C. F. V. Loan,Matrix Computations, 2nd edn. (Johns Hopkins University Press, Baltimore, 1989)","edition":"2nd edn."},{"key":"BF02592148_CR10","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 Review 34 (1992) 167\u2013224.","journal-title":"SIAM Review"},{"key":"BF02592148_CR11","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1287\/mnsc.39.6.757","volume":"39","author":"J. A. Kaliski","year":"1993","unstructured":"J. A. Kaliski and Y. Ye, A short-cut potential reduction algorithm for linear programming,Management Science 39 (1993) 757\u2013773.","journal-title":"Management Science"},{"key":"BF02592148_CR12","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":"BF02592148_CR13","doi-asserted-by":"crossref","unstructured":"L. Khachiyan, On the complexity of approximating extremal determinants in matrices, Preprint (1994).","DOI":"10.1006\/jcom.1995.1005"},{"key":"BF02592148_CR14","first-page":"1093","volume":"244","author":"L. G. Khachiyan","year":"1979","unstructured":"L. G. Khachiyan. A polynomial algorithm in linear programming,Doklady Akademii Nauk SSSR 244 (1979) 1093\u20131086 (translated inSoviet Math. Dokl. 20 (1979) 191\u2013194).","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"BF02592148_CR15","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,Mathematical Programming 44 (1989) 1\u201326.","journal-title":"Mathematical Programming"},{"key":"BF02592148_CR16","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,Linear Algebra and Its Applications 152 (1991) 191\u2013222.","journal-title":"Linear Algebra and Its Applications"},{"key":"BF02592148_CR17","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 applications to the nonlinear complementarity problem.Pacific Journal of Mathematics 88 (1980) 101\u2013161.","journal-title":"Pacific Journal of Mathematics"},{"key":"BF02592148_CR18","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/978-1-4613-9617-8_8","volume-title":"Progress in Mathematical Programming: Interior Point and Related Method","author":"N. Megiddo","year":"1989","unstructured":"N. Megiddo, Pathways to the optimal set in linear programming, in: N. Megiddo, ed.,Progress in Mathematical Programming: Interior Point and Related Method (Springer, New York, 1989) 131\u2013158."},{"key":"BF02592148_CR19","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1287\/moor.14.1.97","volume":"14","author":"N. Megiddo","year":"1989","unstructured":"N. Megiddo and M. Shub, Boundary behavior of interior point algorithms in linear programming,Mathematics of Operations Research 14 (1989) 97\u2013146.","journal-title":"Mathematics of Operations Research"},{"key":"BF02592148_CR20","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,Mathematics of Operations Research 18 (1993) 964\u2013981.","journal-title":"Mathematics of Operations Research"},{"key":"BF02592148_CR21","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1287\/moor.20.1.135","volume":"20","author":"S. Mizuno","year":"1995","unstructured":"S. Mizuno, M.J. Todd and Y. Ye, A surface of analytic centers and infeasible interior-point algorithms for linear programming,Mathematics of Operations Research 20 (1995) 135\u2013162.","journal-title":"Mathematics of Operations Research"},{"key":"BF02592148_CR22","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/BF01587075","volume":"44","author":"R. C. Monteiro","year":"1989","unstructured":"R. C. Monteiro and I. Adler, Interior path following primal-dual algorithm. Part I: linear programming,Mathematical Programming 44 (1989) 27\u201341.","journal-title":"Mathematical Programming"},{"key":"BF02592148_CR23","series-title":"SIAM Studies in Applied Mathematics","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970791","volume-title":"Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms","author":"Y. Nesterov","year":"1994","unstructured":"Y. Nesterov and A. Nemirovskii,Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms, SIAM Studies in Applied Mathematics 13 (SIAM, Philadelphia, 1994)."},{"key":"BF02592148_CR24","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0024-3795(90)90056-I","volume":"132","author":"D. P. O'Leary","year":"1990","unstructured":"D. P. O'Leary, On bounds for scaled projections and pseudoinverses,Linear Algebra and Its Applications 132 (1990) 115\u2013117.","journal-title":"Linear Algebra and Its Applications"},{"key":"BF02592148_CR25","doi-asserted-by":"crossref","unstructured":"J. B. Orlin, A faster strongly polynomial minimum cost flow algorithm, in:Proceedings 20th ACM Symposium on the Theory of Computing (1988) 277\u2013388.","DOI":"10.21236\/ADA457044"},{"key":"BF02592148_CR26","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C. H. Papadimitriou","year":"1982","unstructured":"C. H. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity (Prentice Hall, Englewood Cliff, NJ, 1982)."},{"key":"BF02592148_CR27","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.Mathematical Programming 40 (1988) 59\u201394.","journal-title":"Mathematical Programming"},{"key":"BF02592148_CR28","unstructured":"J. Renegar, Linear Programming, Complexity Theory, and Elementary Functional Analysis, unpublished manuscript, Department of Operations Research and Industrial Engineering, Cornell University (1993)."},{"key":"BF02592148_CR29","series-title":"Technical report","volume-title":"An efficient implementation of a network interior point method","author":"M. G. C. Resende","year":"1992","unstructured":"M. G. C. Resende and G. Veiga, An efficient implementation of a network interior point method, Technical report, Mathematical Sciences Research Center, AT & T Bell Laboratories, Murray Hill, NJ 07974-0636, USA (1992). Revised March 1992, revised version 2.0 August 1992 (to appear inDIMACS Series in Discrete Mathematics and Theoretical Computer Science)."},{"key":"BF02592148_CR30","series-title":"Lecture Notes in Control and Information Sciences","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1007\/BFb0043914","volume-title":"System Modelling and Optimization: Proceedings of the 12th IFIP Conference, Budapest, Hungary (1985)","author":"G. Sonnevend","year":"1986","unstructured":"G. Sonnevend, An \u2018analytic center\u2019 for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, in: A. Prekopa, J. Szelezsan and B. Strazicky, eds.,System Modelling and Optimization: Proceedings of the 12th IFIP Conference, Budapest, Hungary (1985). Lecture Notes in Control and Information Sciences. 84 (Springer Verlag, Berlin, Germany, 1986) 866\u2013876."},{"key":"BF02592148_CR31","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,Mathematical Programming 52 (1991) 527\u2013553.","journal-title":"Mathematical Programming"},{"key":"BF02592148_CR32","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0024-3795(89)90594-6","volume":"112","author":"G. W. Stewart","year":"1989","unstructured":"G. W. Stewart, On scaled projections and pseudoinverses,Linear Algebra and Its Applications 112 (1989) 189\u2013193.","journal-title":"Linear Algebra and Its Applications"},{"key":"BF02592148_CR33","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E. Tardos","year":"1986","unstructured":"E. Tardos, A strongly polynomial algorithm to solve combinatorial linear programs,Operations Research 34 (1986) 250\u2013256.","journal-title":"Operations Research"},{"key":"BF02592148_CR34","doi-asserted-by":"crossref","first-page":"1006","DOI":"10.1287\/opre.38.6.1006","volume":"38","author":"M. J. Todd","year":"1990","unstructured":"M. J. Todd, A Dantzig-Wolfe-like variant of Karmarkar's interior-point linear programming algorithm,Operations Research 38 (1990) 1006\u20131018.","journal-title":"Operations Research"},{"key":"BF02592148_CR35","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF01581252","volume":"59","author":"K. Tone","year":"1993","unstructured":"K. Tone, An active-set strategy in an interior point method for linear programming,Mathematical Programming 59 (1993) 345\u2013360.","journal-title":"Mathematical Programming"},{"key":"BF02592148_CR36","series-title":"Technical Report CORR 93-16","volume-title":"A pseudo-polynomial complexity analysis for interior-point algorithms","author":"L. Tuncel","year":"1993","unstructured":"L. Tuncel, A pseudo-polynomial complexity analysis for interior-point algorithms. Technical Report CORR 93-16, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada (1993)."},{"key":"BF02592148_CR37","volume-title":"Nonlinear Optimization: Complexity Issues","author":"S. A. Vavasis","year":"1991","unstructured":"S. A. Vavasis,Nonlinear Optimization: Complexity Issues (Oxford University Press, New York, 1991)."},{"key":"BF02592148_CR38","series-title":"Technical Report 93-1364","volume-title":"Stable finite elements for problems with wild coefficients","author":"S. A. Vavasis","year":"1993","unstructured":"S. A. Vavasis, Stable finite elements for problems with wild coefficients, Technical Report 93-1364, Department of Computer Science, Cornell University, Ithaca, NY (1993) (to appear inSIAM Journal on Numerical Analysis)."},{"key":"BF02592148_CR39","doi-asserted-by":"crossref","first-page":"1108","DOI":"10.1137\/S0895479892230948","volume":"15","author":"S. A. Vavasis","year":"1994","unstructured":"S. A. Vavasis, Stable numerical algorithms for equilibrium systems,SIAM Journal on Matrix Analysis and Applications 15 (1994) 1108\u20131131.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"BF02592148_CR40","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0167-6377(95)00019-G","volume":"17","author":"S. A. Vavasis","year":"1995","unstructured":"S. A. Vavasis and Y. Ye, Condition numbers for polyhedra with real number data,Operations Research Letters 17 (1995) 209\u2013214.","journal-title":"Operations Research Letters"},{"key":"BF02592148_CR41","doi-asserted-by":"crossref","unstructured":"M. H. Wright, Numerical methods for nonlinearly constrained optimization, Ph. D. Thesis, Stanford University (1976).","DOI":"10.2172\/1453943"},{"key":"BF02592148_CR42","first-page":"341","volume-title":"Acta Numerica 1992","author":"M. H. Wright","year":"1992","unstructured":"M. H. Wright, Interior methods for constrained optimization, in: A. Iserles, ed.,Acta Numerica 1992 (Cambridge University Press, Cambridge, 1992) 341\u2013407."},{"key":"BF02592148_CR43","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,Mathematical Programming 57 (1992) 325\u2013336.","journal-title":"Mathematical Programming"},{"key":"BF02592148_CR44","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF01581242","volume":"59","author":"Y. Ye","year":"1993","unstructured":"Y. Ye O. G\u00fcler, R. A. Tapia and Y. Zhang, A quadratically convergent $$O(\\sqrt n L)$$ -iteration algorithm for linear programming,Mathematical Programming 59 (1993) 151\u2013162.","journal-title":"Mathematical Programming"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02592148.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02592148\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02592148","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T08:18:45Z","timestamp":1736929125000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02592148"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,7]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,7]]}},"alternative-id":["BF02592148"],"URL":"https:\/\/doi.org\/10.1007\/bf02592148","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,7]]}}}