{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T07:59:49Z","timestamp":1761292789907},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,2,18]],"date-time":"2011-02-18T00:00:00Z","timestamp":1297987200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s10898-011-9683-4","type":"journal-article","created":{"date-parts":[[2011,2,17]],"date-time":"2011-02-17T18:45:33Z","timestamp":1297968333000},"page":"255-269","source":"Crossref","is-referenced-by-count":13,"title":["On duality gap in binary quadratic programming"],"prefix":"10.1007","volume":"53","author":[{"given":"X. L.","family":"Sun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C. L.","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. J.","family":"Gao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,2,18]]},"reference":[{"key":"9683_CR1","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/s101070100233","volume":"91","author":"K. Allemand","year":"2001","unstructured":"Allemand K., Fukuda K., Liebling T.M., Steiner E.: A polynomial case of unconstrained zero-one quadratic optimization. Math. Program. 91, 49\u201352 (2001)","journal-title":"Math. Program."},{"key":"9683_CR2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0166-218X(95)00026-N","volume":"65","author":"D. Avis","year":"1996","unstructured":"Avis D., Fukuda K.: Reverse search for enumeration. Discret. Appl. Math. 65, 21\u201346 (1996)","journal-title":"Discret. Appl. Math."},{"key":"9683_CR3","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1137\/S1052623498336930","volume":"11","author":"A. Beck","year":"2000","unstructured":"Beck A., Teboulle M.: Global optimality conditions for quadratic optimization problems with binary constraints. SIAM J. Optim. 11, 179\u2013188 (2000)","journal-title":"SIAM J. Optim."},{"key":"9683_CR4","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1002\/net.20220","volume":"52","author":"W. Ben-Ameur","year":"2008","unstructured":"Ben-Ameur W., Neto J.: Spectral bounds for the maximum cut problem. Networks 52, 8\u201313 (2008)","journal-title":"Networks"},{"key":"9683_CR5","unstructured":"Ben-Tal, A.: Conic and robust optimization. Lecture notes, Universita di Roma La Sapienzia, Rome, Italy (2002)"},{"key":"9683_CR6","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/s10107-005-0637-9","volume":"109","author":"A. Billionnet","year":"2007","unstructured":"Billionnet A., Elloumi S.: Using a mixed integer quadratic programming solver for the unconstrained quadratic 0\u20131 problem. Math. Program. 109, 55\u201368 (2007)","journal-title":"Math. Program."},{"key":"9683_CR7","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s10878-006-9625-0","volume":"12","author":"E. \u00c7ela","year":"2006","unstructured":"\u00c7ela E., Klinz B., Meyer C.: Polynomially solvable cases of the constant rank unconstrained quadratic 0\u20131 programming problem. J. Comb. Optim. 12, 187\u2013215 (2006)","journal-title":"J. Comb. Optim."},{"key":"9683_CR8","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0166-218X(92)90256-A","volume":"36","author":"S.T. Chakradhar","year":"1992","unstructured":"Chakradhar S.T., Bushnell M.: A solvable class of quadratic 0\u20131 programming. Discret. Appl. Math. 36, 233\u2013251 (1992)","journal-title":"Discret. Appl. Math."},{"key":"9683_CR9","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1007\/BF01585184","volume":"62","author":"C. Delorme","year":"1993","unstructured":"Delorme C., Poljak S.: Laplacian eigenvalues and the maximum cut problem. Math. Program. 62, 557\u2013574 (1993)","journal-title":"Math. Program."},{"key":"9683_CR10","doi-asserted-by":"crossref","first-page":"125","DOI":"10.3934\/jimo.2008.4.125","volume":"4","author":"S.C. Fang","year":"2008","unstructured":"Fang S.C., Gao D.Y., Sheu R.L., Wu S.Y.: Canonical dual approach to solve 0\u20131 quadratic programming problems. J. Ind. Manag. Optim. 4, 125\u2013142 (2008)","journal-title":"J. Ind. Manag. Optim."},{"key":"9683_CR11","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/s10898-009-9399-x","volume":"45","author":"D.Y. Gao","year":"2009","unstructured":"Gao D.Y., Ruan N., Sherali H.D.: Solutions and optimality criteria for nonconvex constrained global optimization problems with connections between canonical and Lagrangian duality. J. Glob. Optim. 45, 473\u2013497 (2009)","journal-title":"J. Glob. Optim."},{"key":"9683_CR12","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans M.X., Williamson D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"9683_CR13","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s10589-005-3062-3","volume":"33","author":"H.X. Huang","year":"2006","unstructured":"Huang H.X., Pardalos P.M., Prokopyev O.A.: Lower bound improvement and forcing rule for quadratic binary programming. Comput. Optim. Appl. 33, 187\u2013208 (2006)","journal-title":"Comput. Optim. Appl."},{"key":"9683_CR14","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/978-1-4613-0279-7_6","volume-title":"Advances in Convex Analysis and Global Optimization","author":"C. Lemar\u00e9chal","year":"2001","unstructured":"Lemar\u00e9chal C., Oustry F.: SDP relaxations in combinatorial optimization from a Lagrangian point of view. In: Hadjisavvas, N., Pardalos, P.M. (eds) Advances in Convex Analysis and Global Optimization, pp. 119\u2013134. Kluwer, Dordrecht (2001)"},{"key":"9683_CR15","volume-title":"Nonlinear Integer Programming","author":"D. Li","year":"2006","unstructured":"Li D., Sun X.L.: Nonlinear Integer Programming. Springer, New York (2006)"},{"key":"9683_CR16","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/978-0-387-89496-6_11","volume-title":"Optimization and Optimal Control: Theory and Applications","author":"D. Li","year":"2010","unstructured":"Li D., Sun X.L., Gu S.S., Gao J.J., Liu C.L.: Polynomially solvable cases of binary quadratic programs. In: Chinchuluun, A., Pardalos, P.M., Enkhbat, R., Tseveendorj, I. (eds) Optimization and Optimal Control: Theory and Applications, pp. 199\u2013225. Springer, New York (2010)"},{"key":"9683_CR17","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/s10107-005-0692-2","volume":"107","author":"U. Malik","year":"2006","unstructured":"Malik U., Jaimoukha I.M., Halikias G.D., Gungah S.K.: On the gap between the quadratic integer programming problem and its semidefinite relaxation. Math. Program. 107, 505\u2013515 (2006)","journal-title":"Math. Program."},{"key":"9683_CR18","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970791","volume-title":"Interior-Point Polynomial Methods in Convex Programming","author":"Y. Nesterov","year":"1994","unstructured":"Nesterov Y., Nemirovsky A.: Interior-Point Polynomial Methods in Convex Programming. SIAM, Philadelphia, PA (1994)"},{"key":"9683_CR19","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/103147.103156","volume":"17","author":"P.M. Pardalos","year":"1991","unstructured":"Pardalos P.M.: Construction of test problems in quadratic bivalent programming. ACM Trans. Math. Softw. 17, 74\u201387 (1991)","journal-title":"ACM Trans. Math. Softw."},{"key":"9683_CR20","volume-title":"Topics in Semidefinite and Interior-Point Methods","year":"1998","unstructured":"Pardalos, P.M., Wolkowicz, H. (eds): Topics in Semidefinite and Interior-Point Methods. Fields Institute Communications, American Mathematical Society, Providence (1998)"},{"key":"9683_CR21","volume-title":"Novel Approaches to Hard Discrete Optimization","year":"2003","unstructured":"Pardalos, P.M., Wolkowicz, H. (eds): Novel Approaches to Hard Discrete Optimization. Fields Institute Communications, American Mathematical Society, Providence (2003)"},{"key":"9683_CR22","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1002\/net.3230050405","volume":"5","author":"J.C. Picard","year":"1975","unstructured":"Picard J.C., Ratliff H.D.: Minimum cuts and related problems. Networks 5, 357\u2013370 (1975)","journal-title":"Networks"},{"key":"9683_CR23","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF01100205","volume":"7","author":"S. Poljak","year":"1995","unstructured":"Poljak S., Rendl F., Wolkowicz H.: A recipe for semidefinite relaxation for (0, 1)-quadratic programming. J. Glob. Optim. 7, 51\u201373 (1995)","journal-title":"J. Glob. Optim."},{"key":"9683_CR24","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1287\/moor.20.3.550","volume":"20","author":"S. Poljak","year":"1995","unstructured":"Poljak S., Wolkowicz H.: Convex relaxations of (0\u20131) quadratic programming. Math. Oper. Res. 20, 550\u2013561 (1995)","journal-title":"Math. Oper. Res."},{"key":"9683_CR25","first-page":"1","volume":"25","author":"N.Z. Shor","year":"1987","unstructured":"Shor N.Z.: Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25, 1\u201311 (1987)","journal-title":"Sov. J. Comput. Syst. Sci."},{"key":"9683_CR26","first-page":"137","volume":"6","author":"N. Sleumer","year":"1999","unstructured":"Sleumer N.: Output-sensitive cell enumeration in hyperplane arrangements. Nord. J. Comput. 6, 137\u2013161 (1999)","journal-title":"Nord. J. Comput."},{"key":"9683_CR27","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L. Vandenberghe","year":"1996","unstructured":"Vandenberghe L., Boyd S.: Semidefinite programming. SIAM Rev. 38, 49\u201395 (1996)","journal-title":"SIAM Rev."},{"key":"9683_CR28","volume-title":"Handbook of Semidefinite Programming: Theory, Algorithms, and Applications","year":"2000","unstructured":"Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds): Handbook of Semidefinite Programming: Theory, Algorithms, and Applications. Kluwer Academic Publishers, Dordrecht (2000)"},{"key":"9683_CR29","first-page":"1","volume":"1","author":"T. Zaslavsky","year":"1975","unstructured":"Zaslavsky T.: Facing up to arrangements: face-count formulas for partitions of space by hyperplanes. Mem. Am. Math. Soc. 1, 1\u2013101 (1975)","journal-title":"Mem. Am. Math. Soc."},{"key":"9683_CR30","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1287\/moor.1100.0472","volume":"35","author":"X.J. Zheng","year":"2010","unstructured":"Zheng X.J., Sun X.L., Li D., Xia Y.: Duality gap estimation of linear equality constrained binary quadratic programming. Math. Oper. Res. 35, 864\u2013880 (2010)","journal-title":"Math. Oper. Res."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-011-9683-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10898-011-9683-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-011-9683-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:58:58Z","timestamp":1559278738000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10898-011-9683-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2,18]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["9683"],"URL":"https:\/\/doi.org\/10.1007\/s10898-011-9683-4","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2,18]]}}}