{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T06:53:17Z","timestamp":1759042397271},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1982,12,1]],"date-time":"1982-12-01T00:00:00Z","timestamp":407548800000},"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":[[1982,12]]},"DOI":"10.1007\/bf01585104","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T08:31:50Z","timestamp":1114677110000},"page":"216-224","source":"Crossref","is-referenced-by-count":11,"title":["On the computational complexity of piecewise-linear homotopy algorithms"],"prefix":"10.1007","volume":"24","author":[{"given":"Michael J.","family":"Todd","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/1022003","volume":"22","author":"E. Allgower","year":"1980","unstructured":"E. Allgower and K. Georg, \u201cSimplicial and continuation methods for approximating fixed points\u201d,SIAM Review 22 (1980) 28\u201385.","journal-title":"SIAM Review"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0166-218X(80)90001-3","volume":"2","author":"R.W. Cottle","year":"1980","unstructured":"R.W. Cottle, \u201cObservations on a class of nasty linear complementarity problems\u201d,Discrete Applied Mathematics 2 (1980) 89\u2013112.","journal-title":"Discrete Applied Mathematics"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01584975","volume":"3","author":"B.C. Eaves","year":"1972","unstructured":"B.C. Eaves, \u201cHomotopies for computation of fixed points\u201d,Mathematical Programming 3 (1972) 1\u201322.","journal-title":"Mathematical Programming"},{"key":"CR4","first-page":"73","volume-title":"Nonlinear programming, Proceedings of the Ninth SIAM-AMS Symposium in Applied Mathematics","author":"B.C. Eaves","year":"1976","unstructured":"B.C. Eaves, \u201cA short course in solving equations with PL homotopies\u201d, in: R.W. Cottle and C.E. Lemke, eds.,Nonlinear programming, Proceedings of the Ninth SIAM-AMS Symposium in Applied Mathematics (SIAM, Philadelphia, PA, 1976) pp. 73\u2013143."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF01584991","volume":"3","author":"B.C. Eaves","year":"1972","unstructured":"B.C. Eaves and R. Saigal, \u201cHomotopies for computation of fixed points on unbounded regions\u201d,Mathematical Programming 3 (1972) 225\u2013237.","journal-title":"Mathematical Programming"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.1.1.1","volume":"1","author":"B.C. Eaves","year":"1976","unstructured":"B.C. Eaves and H.E. Scarf, \u201cThe solution of systems of piecewise linear equations\u201d,Mathematics of Operations Research 1 (1976) 1\u201327.","journal-title":"Mathematics of Operations Research"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/BF01588254","volume":"17","author":"Y. Fathi","year":"1979","unstructured":"Y. Fathi, \u201cComputational complexity of LCP's associated with positive definite symmetric matrices\u201d,Mathematical Programming 17 (1979) 335\u2013344.","journal-title":"Mathematical Programming"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"1605","DOI":"10.1002\/j.1538-7305.1965.tb04195.x","volume":"44","author":"J. Katzenelson","year":"1965","unstructured":"J. Katzenelson, \u201cAn algorithm for solving nonlinear resistive networks\u201d,Bell System Technical Journal 44 (1965) 1605\u20131620.","journal-title":"Bell System Technical Journal"},{"key":"CR9","volume-title":"Inequalities III","author":"V. Klee","year":"1972","unstructured":"V. Klee and G.J. Minty, \u201cHow good is the simplex algorithm\u201d, in: O. Shisha, ed.,Inequalities III (Academic Press, New York, 1972)."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/BFb0064322","volume-title":"Functional differential equations and approximation of fixed points, Lecture Notes in Mathematics 730","author":"G. Laan van der","year":"1979","unstructured":"G. van der Laan and A.J.J. Talman, \u201cA restart algorithm without an artificial level for computing fixed points on unbounded regions\u201d, in: H.-O. Peitgen and H.-O. Walther, eds.,Functional differential equations and approximation of fixed points, Lecture Notes in Mathematics 730 (Springer, Berlin, 1979) pp. 247\u2013256."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BF01589331","volume":"20","author":"G. Laan van der","year":"1981","unstructured":"G. van der Laan and A.J.J. Talman, \u201cA class of simplicial restart fixed point algorithms without an extra dimension\u201d,Mathematical Programming 20 (1981) 33\u201348.","journal-title":"Mathematical Programming"},{"key":"CR12","unstructured":"O.H. Merrill, \u201cApplications and extensions of an algorithm that computes fixed points of certain upper semi-continuous point to set mappings\u201d, Ph.D. Dissertation, Department of Industrial Engineering, University of Michigan (1972)."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BFb0120782","volume":"7","author":"K.G. Murty","year":"1978","unstructured":"K.G. Murty, \u201cComputational complexity of complementary pivot methods\u201d,Mathematical Programming Study 7 (1978) 61\u201373.","journal-title":"Mathematical Programming Study"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1287\/moor.1.4.359","volume":"1","author":"R. Saigal","year":"1976","unstructured":"R. Saigal, \u201cOn paths generated by fixed-point algorithms\u201d,Mathematics of Operations Research 1 (1976) 359\u2013380.","journal-title":"Mathematics of Operations Research"},{"key":"CR15","volume-title":"Computation of economic equilibra","author":"H.E. Scarf","year":"1973","unstructured":"H.E. Scarf and T. Hansen,Computation of economic equilibra (Yale University Press, New Haven, CT, 1973)."},{"key":"CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-50327-6","volume-title":"The computation of fixed points and applications","author":"M.J. Todd","year":"1976","unstructured":"M.J. Todd,The computation of fixed points and applications (Springer, Berlin, 1976)."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BFb0120788","volume":"7","author":"M.J. Todd","year":"1978","unstructured":"M.J. Todd, \u201cImproving the convergence of fixed-point algorithms\u201d,Mathematical Programming Study 7 (1978) 151\u2013169.","journal-title":"Mathematical Programming Study"},{"key":"CR18","volume-title":"\u201cFixed-point algorithms that allow restarting without an extra dimension\u201d, Tech. Rep. 379","author":"M.J. Todd","year":"1978","unstructured":"M.J. Todd, \u201cFixed-point algorithms that allow restarting without an extra dimension\u201d, Tech. Rep. 379. School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY (1978)."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1287\/moor.5.2.242","volume":"5","author":"M.J. Todd","year":"1980","unstructured":"M.J. Todd, \u201cTraversing large pieces of linearity in algorithms that solve equations by following piecewise-linear paths\u201d,Mathematics of Operations Research 5 (1980) 242\u2013257.","journal-title":"Mathematics of Operations Research"},{"key":"CR20","volume-title":"\u201cPLALGO: a FORTRAN implementation of a piecewise-linear homotopy algorithm for solving systems of nonlinear equations\u201d, Tech. Rep. 454","author":"M.J. Todd","year":"1980","unstructured":"M.J. Todd, \u201cPLALGO: a FORTRAN implementation of a piecewise-linear homotopy algorithm for solving systems of nonlinear equations\u201d, Tech. Rep. 454, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY (1980)."},{"key":"CR21","volume-title":"\u201cA linear system that can be used in sparse piecewise-linear homotopy algorithms\u201d, Rep. NA\/10","author":"M.J. Todd","year":"1980","unstructured":"M.J. Todd, \u201cA linear system that can be used in sparse piecewise-linear homotopy algorithms\u201d, Rep. NA\/10. Department of Applied Mathematics and Theoretical Physics, University of Cambridge, England (1980)."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF01584229","volume":"21","author":"A.H. Wright","year":"1981","unstructured":"A.H. Wright, \u201cThe octahedral algorithm, a new simplicial fixed point algorithm\u201d,Mathematical Programming 21 (1981) 47\u201369.","journal-title":"Mathematical Programming"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585104.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01585104\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T15:32:26Z","timestamp":1556897546000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01585104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,12]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1982,12]]}},"alternative-id":["BF01585104"],"URL":"https:\/\/doi.org\/10.1007\/bf01585104","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1982,12]]}}}