{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T05:01:04Z","timestamp":1772082064063,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1992,5,1]],"date-time":"1992-05-01T00:00:00Z","timestamp":704678400000},"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":[[1992,5]]},"DOI":"10.1007\/bf01581088","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T09:52:15Z","timestamp":1114681935000},"page":"337-339","source":"Crossref","is-referenced-by-count":31,"title":["Open questions in complexity theory for numerical optimization"],"prefix":"10.1007","volume":"57","author":[{"given":"Panos M.","family":"Pardalos","sequence":"first","affiliation":[]},{"given":"Stephen A.","family":"Vavasis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","volume-title":"The complexity of approximating a non-linear program","author":"M. Bellare","year":"1992","unstructured":"M. Bellare and P. Rogaway, \u201cThe complexity of approximating a non-linear program,\u201d unpublished manuscript, IBM T.J. Watson Research Center (Yorktown Heights, NY, 1992)."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1137\/0213003","volume":"13","author":"M.E. Dyer","year":"1984","unstructured":"M.E. Dyer, \u201cLinear time algorithms for two- and three-variable linear programs,\u201dSIAM Journal on Computing 13 (1984) 31\u201345.","journal-title":"SIAM Journal on Computing"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BF02283688","volume":"25","author":"G.M. Guisewite","year":"1990","unstructured":"G.M. Guisewite and P.M. Pardalos, \u201cMinimum concave-cost network flow problems: Applications, complexity, and algorithms,\u201dAnnals of Operations Research 25 (1990) 75\u2013100.","journal-title":"Annals of Operations Research"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"G.M. Guisewite and P.M. Pardalos, \u201cA polynomially solvable concave network flow problem,\u201d to appear in:Networks (1992).","DOI":"10.1002\/net.3230230208"},{"key":"CR5","unstructured":"C.-G. Han, P.M. Pardalos and Y. Ye, \u201cAn interior point algorithm for indefinite quadratic programming,\u201d manuscript (1991)."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"D.S. Johnson","year":"1988","unstructured":"D.S. Johnson, C.H. Papadimitriou and M. Yannakakis, \u201cHow easy is local search,\u201dJournal of Computer and System Sciences 37 (1988) 79\u2013100.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1287\/mnsc.11.7.681","volume":"11","author":"C.E. Lemke","year":"1965","unstructured":"C.E. Lemke, \u201cBimatrix equilibrium points and mathematical programming,\u201dManagement Science 11 (1965) 681\u2013689.","journal-title":"Management Science"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N. Megiddo","year":"1984","unstructured":"N. Megiddo, \u201cLinear programming in linear time when the dimension is fixed,\u201dJournal of the ACM 31 (1984) 114\u2013127.","journal-title":"Journal of the ACM"},{"key":"CR9","volume-title":"\u201cA note on the complexity of P-matrix LCP and computing an equilibrium,\u201d Research Report RJ 6439","author":"N. Megiddo","year":"1988","unstructured":"N. Megiddo, \u201cA note on the complexity of P-matrix LCP and computing an equilibrium,\u201d Research Report RJ 6439, IBM Almaden Research Center (San Jose, CA, 1988)."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/BF01588800","volume":"49","author":"J.J. Mor\u00e9","year":"1991","unstructured":"J.J. Mor\u00e9 and S.A. Vavasis, \u201cOn the solution of concave knapsack problems,\u201dMathematical Programming 49 (1991) 397\u2013411.","journal-title":"Mathematical Programming"},{"key":"CR11","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,\u201dMathematical Programming Study 7 (1978) 61\u201373.","journal-title":"Mathematical Programming Study"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"K.G. Murty","year":"1987","unstructured":"K.G. Murty and S.N. Kabadi, \u201cSome NP-complete problems in quadratic and nonlinear programming,\u201dMathematical Programming 39 (1987) 117\u2013129.","journal-title":"Mathematical Programming"},{"key":"CR13","volume-title":"On the complexity of the parity argument and other inefficient proofs of existence","author":"C.H. Papadimitriou","year":"1992","unstructured":"C.H. Papadimitriou, \u201cOn the complexity of the parity argument and other inefficient proofs of existence,\u201d unpublished manuscript, University of California at San Diego (La Jolla, CA, 1992)."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0167-6377(88)90049-1","volume":"7","author":"P.M. Pardalos","year":"1988","unstructured":"P.M. Pardalos and G. Schnitger, \u201cChecking local optimality in constrained quadratic programming is NP-hard,\u201dOperations Research Letters 7 (1988) 33\u201345.","journal-title":"Operations Research Letters"},{"key":"CR15","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,\u201dJournal of Global Optimization 1 (1991) 15\u201322.","journal-title":"Journal of Global Optimization"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"\u00c9. Tardos","year":"1986","unstructured":"\u00c9. Tardos, \u201cA strongly polynomial algorithm to solve combinatorial linear programs,\u201dOperations Research 34 (1986) 250\u2013256.","journal-title":"Operations Research"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0167-6377(82)90047-5","volume":"1","author":"J.F. Traub","year":"1982","unstructured":"J.F. Traub and H. Wo\u017aniakowski, \u201cComplexity of linear programming,\u201dOperations Research Letters 1 (1982) 59\u201362.","journal-title":"Operations Research Letters"},{"key":"CR18","volume-title":"Nonlinear Optimization: Complexity Issues","author":"S.A. Vavasis","year":"1991","unstructured":"S.A. Vavasis,Nonlinear Optimization: Complexity Issues (Oxford University Press, Oxford, 1991)."},{"key":"CR19","first-page":"1","volume-title":"Recent Advances in Global Optimization","author":"S.A. Vavasis","year":"1992","unstructured":"S.A. Vavasis, \u201cOn approximation algorithms for concave quadratic programming,\u201d in: C.A. Floudas and P. Pardalos, eds.,Recent Advances in Global Optimization (Princeton University Press, Princeton, NJ, 1992a) pp. 1\u201318."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF01581085","volume":"57","author":"S.A. Vavasis","year":"1992","unstructured":"S.A. Vavasis, \u201cApproximation algorithms for indefinite quadratic programming,\u201dMathematical Programming (Series B) 57 (1992b) 279\u2013311, this issue.","journal-title":"Mathematical Programming (Series B)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01581088.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01581088\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01581088","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T03:55:59Z","timestamp":1586231759000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01581088"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,5]]},"references-count":20,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1992,5]]}},"alternative-id":["BF01581088"],"URL":"https:\/\/doi.org\/10.1007\/bf01581088","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,5]]}}}