{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T12:08:35Z","timestamp":1783080515010,"version":"3.54.6"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2016,6,18]],"date-time":"2016-06-18T00:00:00Z","timestamp":1466208000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s10107-016-1036-0","type":"journal-article","created":{"date-parts":[[2016,6,18]],"date-time":"2016-06-18T18:21:08Z","timestamp":1466274068000},"page":"225-240","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":79,"title":["Mixed-integer quadratic programming is in NP"],"prefix":"10.1007","volume":"162","author":[{"given":"Alberto Del","family":"Pia","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Santanu S.","family":"Dey","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Molinaro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,6,18]]},"reference":[{"key":"1036_CR1","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1090\/S0002-9939-1976-0396605-3","volume":"55","author":"I Borosh","year":"1976","unstructured":"Borosh, I., Treybig, L.B.: Bounds on positive integral solutions to linear Diophantine equations. Proc. Am. Math. Soc. 55, 299\u2013304 (1976)","journal-title":"Proc. Am. Math. Soc."},{"issue":"1\u20133","key":"1036_CR2","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF01580858","volume":"47","author":"W Cook","year":"1990","unstructured":"Cook, W., Kannan, R., Schrijver, A.: Chv\u00e1tal closures for mixed integer programming problems. Math. Program. 47(1\u20133), 155\u2013174 (1990)","journal-title":"Math. Program."},{"key":"1036_CR3","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/s10107-007-0175-8","volume":"118","author":"J Loera De","year":"2008","unstructured":"De Loera, J., Hemmecke, R., K\u00f6ppe, M., Weismantel, R.: FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension. Math. Program., Ser. A 118, 273\u2013290 (2008)","journal-title":"Math. Program., Ser. A"},{"key":"1036_CR4","doi-asserted-by":"crossref","unstructured":"Del Pia, A., Weismantel, R.: Integer quadratic programming in the plane. In: Chekuri, C. (ed.) SODA, pp. 840\u2013846. SIAM (2014)","DOI":"10.1137\/1.9781611973402.62"},{"issue":"3","key":"1036_CR5","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M Garey","year":"1976","unstructured":"Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"1036_CR6","unstructured":"Hartmann, M.: Cutting planes and the complexity of the integer hull. Tech. Rep. 819, School of Operations Research and Industrial Engineering, Cornell University (1989)"},{"key":"1036_CR7","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/j.orl.2015.03.002","volume":"43","author":"R Hildebrand","year":"2015","unstructured":"Hildebrand, R., Oertel, T., Weismantel, R.: Note on the complexity of the mixed-integer hull of a polyhedron. Oper. Res. Lett. 43, 279\u2013282 (2015)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1036_CR8","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1287\/opre.21.1.221","volume":"21","author":"R Jeroslow","year":"1973","unstructured":"Jeroslow, R.: There cannot be any algorithm for integer programming with quadratic constraints. Oper. Res. 21(1), 221\u2013224 (1973)","journal-title":"Oper. Res."},{"key":"1036_CR9","doi-asserted-by":"crossref","unstructured":"Kannan, R., Monma, C.L.: On the computational complexity of integer programming problems. In: Henn, R., Korte, B., Oettli, W. (eds.) Lecture Notes in Economics and Mathematical Systems, vol. 157, pp. 161\u2013172. Springer, Heidelberg (1978)","DOI":"10.1007\/978-3-642-95322-4_17"},{"key":"1036_CR10","doi-asserted-by":"crossref","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Millera, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations. New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1036_CR11","unstructured":"Khachiyan, L.: Convexity and complexity in polynomial programming. In: Proceedings of the International Congress of Mathematicians, pp. 1569\u20131577. Warsaw (1983)"},{"key":"1036_CR12","doi-asserted-by":"publisher","unstructured":"Koeppe, M.: On the complexity of nonlinear mixed-integer optimization. In: Lee, J., Leyffer, S. (eds.) Mixed Integer Nonlinear Programming, The IMA Volumes in Mathematics and its Applications, vol. 154, pp. 533\u2013557. Springer, New York (2012). doi: 10.1007\/978-1-4614-1927_19","DOI":"10.1007\/978-1-4614-1927_19"},{"key":"1036_CR13","first-page":"485","volume":"260","author":"JC Lagarias","year":"1980","unstructured":"Lagarias, J.C.: On the computational complexity of determining the solvability or unsolvability of the equation $$x^2 - dy^2 = -1$$ x 2 - d y 2 = - 1 . Trans. Am. Math. Soc. 260, 485\u2013508 (1980)","journal-title":"Trans. Am. Math. Soc."},{"key":"1036_CR14","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"K Murty","year":"1987","unstructured":"Murty, K., Kabadi, S.: Some NP-complete problems in quadratin and nonlinear programming. Math. Program. 39, 117\u2013129 (1987)","journal-title":"Math. Program."},{"key":"1036_CR15","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1145\/322276.322287","volume":"28","author":"CH Papadimitriou","year":"1981","unstructured":"Papadimitriou, C.H.: On the complexity of integer programming. J. Assoc. Comput. Mach. 28, 765\u2013768 (1981)","journal-title":"J. Assoc. Comput. Mach."},{"key":"1036_CR16","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)"},{"issue":"2","key":"1036_CR17","doi-asserted-by":"crossref","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."},{"key":"1036_CR18","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1090\/S0002-9939-1978-0500555-0","volume":"72","author":"J zur Gathen von","year":"1978","unstructured":"von zur Gathen, J., Sieveking, M.: A bound on solutions of linear integer equalities and inequalities. Proc. Am. Math. Soc. 72, 155\u2013158 (1978)","journal-title":"Proc. Am. Math. Soc."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1036-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-016-1036-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1036-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1036-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T16:39:23Z","timestamp":1498322363000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-016-1036-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,18]]},"references-count":18,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["1036"],"URL":"https:\/\/doi.org\/10.1007\/s10107-016-1036-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,18]]}}}