{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T18:56:56Z","timestamp":1649185016530},"reference-count":20,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2000,12,1]],"date-time":"2000-12-01T00:00:00Z","timestamp":975628800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4611,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2000,12]]},"DOI":"10.1016\/s0166-218x(00)00263-8","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T16:56:47Z","timestamp":1027616207000},"page":"225-239","source":"Crossref","is-referenced-by-count":2,"title":["Bounds and fast approximation algorithms for binary quadratic optimization problems with application to MAX 2SAT"],"prefix":"10.1016","volume":"107","author":[{"given":"Hans","family":"van Maaren","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joost P.","family":"Warners","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(00)00263-8_BIB1","unstructured":"F. Alizadeh, Combinatorial optimization with interior point methods and semi\u2013definite matrices, Ph.D. Thesis, University of Minnesota, Minneapolis, USA, 1991."},{"issue":"3","key":"10.1016\/S0166-218X(00)00263-8_BIB2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","article-title":"A linear-time algorithm for testing the truth of certain quantified Boolean formulas","volume":"8","author":"Aspvall","year":"1979","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0166-218X(00)00263-8_BIB3","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1007\/BF01585184","article-title":"Laplacian eigenvalues and the maximum cut problem","volume":"62","author":"Delorme","year":"1993","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(00)00263-8_BIB4","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0012-365X(93)90151-I","article-title":"The performance of an eigenvalue bound on the max-cut problem in some classes of graphs","volume":"111","author":"Delorme","year":"1993","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(00)00263-8_BIB5","doi-asserted-by":"crossref","unstructured":"D. Du, J. Gu, P.M. Pardalos (Eds.), Satisfiability Problem: Theory and Applications, DIMACS Series in Discrete Mathematics and Computer Science, Vol. 35, American Mathematical Society, Providence, RI, 1997.","DOI":"10.1090\/dimacs\/035"},{"key":"10.1016\/S0166-218X(00)00263-8_BIB6","doi-asserted-by":"crossref","unstructured":"U. Feige, M. Goemans, Approximating the value of two prover proof systems with applications to MAX 2SAT and MAX DICUT, Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 182\u2013189.","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"10.1016\/S0166-218X(00)00263-8_BIB7","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","article-title":"Some simplified NP-complete graph problems","volume":"1","author":"Garey","year":"1976","journal-title":"Theoret. Comput. Sci."},{"issue":"6","key":"10.1016\/S0166-218X(00)00263-8_BIB8","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","article-title":"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming","volume":"42","author":"Goemans","year":"1995","journal-title":"J. ACM"},{"key":"10.1016\/S0166-218X(00)00263-8_BIB9","unstructured":"P.L. Hammer, A.A. Rubin, Some remarks on quadratic programming with 0\u20131 variables, Rev. Fran\u00e7aise Informat. Recherche Op\u00e9rationelle 4 (1970) ser. V-3, 67\u201379."},{"issue":"2","key":"10.1016\/S0166-218X(00)00263-8_BIB10","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1137\/0806020","article-title":"An interior-point method for semidefinite programming","volume":"6","author":"Helmberg","year":"1996","journal-title":"SIAM J. Optim."},{"key":"10.1016\/S0166-218X(00)00263-8_BIB11","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","article-title":"Approximation algorithms for combinatorial problems","volume":"9","author":"Johnson","year":"1974","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0166-218X(00)00263-8_BIB12","doi-asserted-by":"crossref","unstructured":"S. Joy, J. Mitchell, B. Borchers, A branch and cut algorithm for MAX-SAT and weighted MAX-SAT, in: D. Du, J. Gu, P.M. Pardalos (Eds.), Satisfiability Problem: Theory and Applications, DIMACS Series in Discrete Mathematics and Computer Science, Vol. 35, American Mathematical Society, Providence, RI, 1997.","DOI":"10.1090\/dimacs\/035\/13"},{"key":"10.1016\/S0166-218X(00)00263-8_BIB13","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/BF01582907","article-title":"An interior point algorithm to solve computationally difficult set covering problems","volume":"52","author":"Karmarkar","year":"1991","journal-title":"Math. Programming"},{"issue":"5","key":"10.1016\/S0166-218X(00)00263-8_BIB14","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1080\/02331938808843386","article-title":"A tight bound for the Boolean quadratic optimization problem and its use in a branch and bound algorithm","volume":"19","author":"K\u00f6rner","year":"1988","journal-title":"Optimization"},{"issue":"3","key":"10.1016\/S0166-218X(00)00263-8_BIB15","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1016\/0377-2217(90)90016-5","article-title":"On duality for Boolean programming","volume":"46","author":"K\u00f6rner","year":"1990","journal-title":"European J. Oper. Res."},{"key":"10.1016\/S0166-218X(00)00263-8_BIB16","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/S0166-218X(99)00041-4","article-title":"Elliptic approximations of propositional formulae","volume":"96\u201397","author":"Van Maaren","year":"1999","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(00)00263-8_BIB17","doi-asserted-by":"crossref","unstructured":"H. Van Maaren, On the use of second order derivatives for the satisfiability problems, in: D. Du, J. Gu, P.M. Pardalos (Eds.), Satisfiability Problem: Theory and Applications, DIMACS Series in Discrete Mathematics and Computer Science, Vol. 35, American Mathematical Society, Providence, RI, 1997, pp. 677\u2013687.","DOI":"10.1090\/dimacs\/035\/21"},{"key":"10.1016\/S0166-218X(00)00263-8_BIB18","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0166-218X(94)00155-7","article-title":"Solving the max-cut problem using eigenvalues","volume":"62","author":"Poljak","year":"1995","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(00)00263-8_BIB19","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0020-0190(98)00144-6","article-title":"A linear\u2013time transformation of linear inequalities into conjunctive normal form","volume":"68","author":"Warners","year":"1998","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0166-218X(00)00263-8_BIB20","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/BF01580903","article-title":"On affine scaling algorithms for nonconvex quadratic programming","volume":"56","author":"Ye","year":"1992","journal-title":"Math. Programming"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X00002638?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X00002638?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T18:50:41Z","timestamp":1555786241000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X00002638"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,12]]},"references-count":20,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2000,12]]}},"alternative-id":["S0166218X00002638"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(00)00263-8","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2000,12]]}}}