{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:52:02Z","timestamp":1781077922739,"version":"3.54.1"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2022,1,4]],"date-time":"2022-01-04T00:00:00Z","timestamp":1641254400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,4]],"date-time":"2022-01-04T00:00:00Z","timestamp":1641254400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,9]]},"DOI":"10.1007\/s10107-021-01714-2","type":"journal-article","created":{"date-parts":[[2022,1,4]],"date-time":"2022-01-04T00:03:16Z","timestamp":1641254596000},"page":"783-792","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["On the complexity of finding a local minimizer of a quadratic function over a polytope"],"prefix":"10.1007","volume":"195","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1590-7281","authenticated-orcid":false,"given":"Amir Ali","family":"Ahmadi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,1,4]]},"reference":[{"key":"1714_CR1","doi-asserted-by":"publisher","unstructured":"Ahmadi, A.A., Hall, G.: On the complexity of detecting convexity over a box. Math. Program. 182, 429\u2013443 (2020). https:\/\/doi.org\/10.1007\/s10107-019-01396-x","DOI":"10.1007\/s10107-019-01396-x"},{"key":"1714_CR2","doi-asserted-by":"publisher","unstructured":"Ahmadi, A.A., Zhang, J.: Complexity aspects of local minima and related notions, Adv. Math. (2021). https:\/\/doi.org\/10.1016\/j.aim.2021.108119","DOI":"10.1016\/j.aim.2021.108119"},{"issue":"4","key":"1714_CR3","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/S1052623401383248","volume":"12","author":"E De Klerk","year":"2002","unstructured":"De Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875\u2013892 (2002)","journal-title":"SIAM J. Optim."},{"key":"1714_CR4","volume-title":"Computers and Intractability","author":"MR Garey","year":"2002","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. WH Freeman, New York (2002)"},{"issue":"4","key":"1714_CR5","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/2421119.2421135","volume":"43","author":"LA Hemaspaandra","year":"2012","unstructured":"Hemaspaandra, L.A., Williams, R.: SIGACT news complexity theory column 76: an atypical survey of typical-case heuristic algorithms. ACM SIGACT News 43(4), 70\u201389 (2012)","journal-title":"ACM SIGACT News"},{"key":"1714_CR6","doi-asserted-by":"crossref","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. In: Proceedings of the 16th annual ACM symposium on theory of computing, pp. 302\u2013311 (1984)","DOI":"10.1145\/800057.808695"},{"key":"1714_CR7","unstructured":"Khachiyan, L.G.: A polynomial algorithm in linear programming. In: Doklady Akademii Nauk, vol. 244, pp. 1093\u20131096. Russian Academy of Sciences (1979)"},{"key":"1714_CR8","doi-asserted-by":"crossref","unstructured":"Kozlov, M.K., Tarasov, S.P., Khachiyan, L.G.: The polynomial solvability of convex quadratic programming. USSR Comput Math Math Phys 20(5), 223\u2013228 (1980)","DOI":"10.1016\/0041-5553(80)90098-1"},{"issue":"1\u20133","key":"1714_CR9","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/BF01588800","volume":"49","author":"JJ Mor\u00e9","year":"1990","unstructured":"Mor\u00e9, J.J., Vavasis, S.A.: On the solution of concave knapsack problems. Math. Program. 49(1\u20133), 397\u2013411 (1990)","journal-title":"Math. Program."},{"key":"1714_CR10","doi-asserted-by":"publisher","first-page":"533","DOI":"10.4153\/CJM-1965-053-6","volume":"17","author":"TS Motzkin","year":"1965","unstructured":"Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Tur\u00e1n. Can. J. Math. 17, 533\u2013540 (1965)","journal-title":"Can. J. Math."},{"issue":"2","key":"1714_CR11","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"KG Murty","year":"1987","unstructured":"Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39(2), 117\u2013129 (1987)","journal-title":"Math. Program."},{"issue":"1","key":"1714_CR12","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0167-6377(88)90049-1","volume":"7","author":"PM Pardalos","year":"1988","unstructured":"Pardalos, P.M., Schnitger, G.: Checking local optimality in constrained quadratic programming is NP-hard. Oper. Res. Lett. 7(1), 33\u201335 (1988)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1714_CR13","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF00120662","volume":"1","author":"PM Pardalos","year":"1991","unstructured":"Pardalos, P.M., Vavasis, S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Global Optim. 1(1), 15\u201322 (1991)","journal-title":"J. Global Optim."},{"issue":"1\u20133","key":"1714_CR14","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF01581088","volume":"57","author":"PM Pardalos","year":"1992","unstructured":"Pardalos, P.M., Vavasis, S.A.: Open questions in complexity theory for numerical optimization. Math. Program. 57(1\u20133), 337\u2013339 (1992)","journal-title":"Math. Program."},{"issue":"2","key":"1714_CR15","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0020-0190(90)90100-C","volume":"36","author":"SA Vavasis","year":"1990","unstructured":"Vavasis, S.A.: Quadratic programming is in NP. Inf. Process. Lett. 36(2), 73\u201377 (1990)","journal-title":"Inf. Process. Lett."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01714-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01714-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01714-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T15:38:22Z","timestamp":1666366702000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01714-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,4]]},"references-count":15,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["1714"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01714-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,4]]},"assertion":[{"value":"16 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 September 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}