{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T21:32:36Z","timestamp":1770499956791,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1992,11,1]],"date-time":"1992-11-01T00:00:00Z","timestamp":720576000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Optim Applic"],"published-print":{"date-parts":[[1992,11]]},"DOI":"10.1007\/bf00253808","type":"journal-article","created":{"date-parts":[[2004,9,27]],"date-time":"2004-09-27T02:54:33Z","timestamp":1096253673000},"page":"227-239","source":"Crossref","is-referenced-by-count":27,"title":["Parametric simplex algorithms for a class of NP-Complete problems whose average number of steps is polynomial"],"prefix":"10.1007","volume":"1","author":[{"given":"Hiroshi","family":"Konno","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takahito","family":"Kuno","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasutoshi","family":"Yajima","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF00253808_CR1","series-title":"Tech. Report","volume-title":"The expected number of pivots needed to solve parametric linear programs and the efficiency of the self-dual simplex method","author":"I. Adler","year":"1983","unstructured":"I. Adler, \u201cThe expected number of pivots needed to solve parametric linear programs and the efficiency of the self-dual simplex method\u201d, Department of IEOR, University of California, Berkeley, CA, Tech. Report, 1983."},{"key":"BF00253808_CR2","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1287\/moor.11.4.570","volume":"11","author":"I. Adler","year":"1986","unstructured":"I. Adler, R. Karp, and R. Shamir, \u201cA family of simplex variants solving an m\u00d7d linear program in expected number of pivot steps depending on d only\u201d, Math. of Oper. Res., vol. 11, 570\u2013590, 1986.","journal-title":"Math. of Oper. Res."},{"key":"BF00253808_CR3","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1145\/4221.4222","volume":"32","author":"I. Adler","year":"1985","unstructured":"I. Adler and N. Megiddo, \u201cA simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension\u201d, J. of the ACM, vol. 32, 871\u2013895, 1985.","journal-title":"J. of the ACM"},{"key":"BF00253808_CR4","unstructured":"K.H. Borgwardt, The Simplex Methods: A Probabilistic Analysis, Springer-Verlag: 1982."},{"key":"BF00253808_CR5","volume-title":"Linear Programming","author":"V. Chv\u00e1tal","year":"1983","unstructured":"V. Chv\u00e1tal, Linear Programming W.H. Freeman and Company: New York, NY, 1983."},{"key":"BF00253808_CR6","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1002\/nav.3800020106","volume":"2","author":"S.I. Gass","year":"1955","unstructured":"S.I. Gass and E.L. Saaty, \u201cThe computational algorithm for the parametric objective function\u201d, Nav. Res. Logistics Q., vol. 2, pp. 39\u201345, 1955.","journal-title":"Nav. Res. Logistics Q."},{"key":"BF00253808_CR7","series-title":"Tech. Report","volume-title":"The simplex algorithm is very good!! \u2014 on the expected number of pivot steps and related properties of random linear programs (draft)","author":"M. Haimovich","year":"1983","unstructured":"M. Haimovich, \u201cThe simplex algorithm is very good!! \u2014 on the expected number of pivot steps and related properties of random linear programs (draft)\u201d, Uris Hall, Columbia University, New York, NY, Tech. Report, 1983."},{"key":"BF00253808_CR8","volume-title":"The Traveling Salesman Problem","author":"R.M. Karp","year":"1985","unstructured":"R.M. Karp and J.M. Steele, \u201cProbabilistic analysis of heuristics\u201d, in The Traveling Salesman Problem, (E.L. Lawler, et al., eds.), John Wiley and Sons: New York, NY, 1985."},{"key":"BF00253808_CR9","first-page":"1093","volume":"244","author":"L.G. Khachian","year":"1979","unstructured":"L.G. Khachian, \u201cA polynomial algorithm for linear programming\u201d, Dokla. Akad. Nauk. USSR, vol. 244, 1093\u20131096, 1979.","journal-title":"Dokla. Akad. Nauk. USSR"},{"key":"BF00253808_CR10","series-title":"IHSS Report 91-37","volume-title":"Computational complexity of the linear multiplicative programming problem","author":"H. Konno","year":"1991","unstructured":"H. Konno, \u201cComputational complexity of the linear multiplicative programming problem\u201d, Institute of Human and Social Sciences, Tokyo Institute of Technology, Tokyo, IHSS Report 91-37, 1991."},{"key":"BF00253808_CR11","unstructured":"H. Konno and Y. Yajima, \u201cSolving rank two bilinear programs by parametric simplex algorithms\u201d, Institute of Human and Social Sciences, Tokyo Institute of Technology, Tokyo, IHSS Report 90-17,"},{"key":"BF00253808_CR12","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF00120666","volume":"1","author":"H. Konno","year":"1991","unstructured":"H. Konno, Y. Yajima, and T. Matsui, \u201cParametric simplex algorithm for solving special class of nonconvex minimization problems\u201d, J. of Global Optimization, vol. 1, 65\u201381, 1991.","journal-title":"J. of Global Optimization"},{"key":"BF00253808_CR13","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1287\/opre.26.2.347","volume":"26","author":"J.K. Lenstra","year":"1978","unstructured":"J.K. Lenstra and A.H.G. Rinnooy Kan, \u201cOn the expected performance of Branch-and-bound algorithm\u201d, Oper. Res., vol. 26, 347\u2013349, 1978.","journal-title":"Oper. Res."},{"key":"BF00253808_CR14","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF01580648","volume":"35","author":"N. Megiddo","year":"1986","unstructured":"N. Megiddo, \u201cOn the expected number of linear complementary cones intersected by random and semi-random rays\u201d, Math. Programming, vol. 35, 225\u2013235, 1986.","journal-title":"Math. Programming"},{"key":"BF00253808_CR15","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/BF01581642","volume":"19","author":"K.G. Murty","year":"1980","unstructured":"K.G. Murty, \u201cComputational complexity of parametric linear programming\u201d, Math. Programming, vol. 19, 213\u2013219, 1980.","journal-title":"Math. Programming"},{"key":"BF00253808_CR16","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1080\/02331939008843615","volume":"21","author":"P.M. Pardalos","year":"1990","unstructured":"P.M. Pardalos, \u201cPolynomial time algorithms for some classes of constrained nonconvex quadratic problems\u201d, Optimization, vol. 21, 483\u2013853, 1990.","journal-title":"Optimization"},{"key":"BF00253808_CR17","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0898-1221(91)90163-X","volume":"21","author":"P.M. Pardalos","year":"1991","unstructured":"P.M. Pardalos, \u201cGlobal optimization algorithms for linear constrained indefinite quadratic problems\u201d, Computers Math. Appl., vol. 21, 87\u201397, 1991.","journal-title":"Computers Math. Appl."},{"key":"BF00253808_CR18","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF00120662","volume":"1","author":"P.M. Pardalos","year":"1991","unstructured":"P.M. Pardalos and S.A. Vavasis, \u201cQuadratic programming with one negative eigenvalue is NP-hard\u201d, J. of Global Optimization, vol. 1, 15\u201322, 1991.","journal-title":"J. of Global Optimization"},{"key":"BF00253808_CR19","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1986","unstructured":"A. Schrijver, Theory of Linear and Integer Programming, John-Wiley & Sons: New York, NY, 1986."},{"key":"BF00253808_CR20","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1287\/mnsc.33.3.301","volume":"33","author":"R. Shamir","year":"1987","unstructured":"R. Shamir, \u201cThe efficiency of the simplex method: a survey\u201d, Management Sci. vol. 33, 301\u2013334, 1987.","journal-title":"Management Sci."},{"key":"BF00253808_CR21","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/BF02591902","volume":"27","author":"S. Smale","year":"1983","unstructured":"S. Smale, \u201cOn the average speed of the simplex method of linear programming\u201d, Math. Programming, vol. 27, 241\u2013262, 1983.","journal-title":"Math. Programming"},{"key":"BF00253808_CR22","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF01580646","volume":"35","author":"M.J. Todd","year":"1986","unstructured":"M.J. Todd, \u201cPolynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems\u201d, Math. Programming, vol. 35, 173\u2013192, 1986.","journal-title":"Math. Programming"},{"key":"BF00253808_CR23","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0020-0190(90)90100-C","volume":"36","author":"S.A. Vavasis","year":"1990","unstructured":"S.A. Vavasis, \u201cQuadratic programming is in NP\u201d, Information Processing Letters, vol. 36, 73\u201377, 1990.","journal-title":"Information Processing Letters"},{"key":"BF00253808_CR24","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF00119989","volume":"1","author":"Y. Yajima","year":"1990","unstructured":"Y. Yajima and H. Konno, \u201cEfficient algorithms for solving rank two and rank three bilinear programming problems\u201d, Global Optimization, vol. 1, 155\u2013171, 1990.","journal-title":"Global Optimization"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00253808.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00253808\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00253808","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,3]],"date-time":"2019-04-03T15:56:52Z","timestamp":1554307012000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00253808"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,11]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,11]]}},"alternative-id":["BF00253808"],"URL":"https:\/\/doi.org\/10.1007\/bf00253808","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,11]]}}}