{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T10:46:42Z","timestamp":1763808402323,"version":"3.40.5"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2003,3,1]],"date-time":"2003-03-01T00:00:00Z","timestamp":1046476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2003,3,1]],"date-time":"2003-03-01T00:00:00Z","timestamp":1046476800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Annals of Mathematics and Artificial Intelligence"],"published-print":{"date-parts":[[2003,3]]},"DOI":"10.1023\/a:1021208315170","type":"journal-article","created":{"date-parts":[[2003,3,21]],"date-time":"2003-03-21T00:56:49Z","timestamp":1048208209000},"page":"285-305","source":"Crossref","is-referenced-by-count":9,"title":["On Semidefinite Programming Relaxations of (2+p)-SAT"],"prefix":"10.1007","volume":"37","author":[{"given":"E.","family":"de Klerk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H.","family":"van Maaren","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-2","key":"5098008_CR1","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0304-3975(01)00154-2","volume":"265","author":"D. Achlioptas","year":"2001","unstructured":"D. Achlioptas, L.M. Kirousis, E. Kranakis and D. Krizank, Rigorous results for random (2+p)-SAT, Theoretical Computer Science 265(1-2) (2001) 109\u2013129.","journal-title":"Theoretical Computer Science"},{"key":"5098008_CR2","series-title":"Encyclopedia of Mathematical Sciences","volume-title":"Geometry II","author":"D.V. Alekseevskij","year":"1993","unstructured":"D.V. Alekseevskij, E.B. Vinberg and A.S. Solodovnikov, Geometry of spaces of constant curvature, in: Geometry II, ed. E.B. Vinberg, Encyclopedia of Mathematical Sciences, Vol. 29 (Springer, Berlin, 1993)."},{"key":"5098008_CR3","volume-title":"Nonlinear Programming: Theory and Algorithms","author":"M.S. Bazarraa","year":"1993","unstructured":"M.S. Bazarraa, H.D. Sherali and C.M. Shetty, Nonlinear Programming: Theory and Algorithms, 2nd edn. (Wiley, New York, 1993).","edition":"2nd edn."},{"key":"5098008_CR4","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1137\/S1052623497328008","volume":"10","author":"S.J. Benson","year":"2000","unstructured":"S.J. Benson, Y. Ye and X. Zhang, Solving large-scale sparse semidefinite programs for combinatorial optimization, SIAM Journal on Optimization 10 (2000) 443\u2013461.","journal-title":"SIAM Journal on Optimization"},{"key":"5098008_CR5","series-title":"Working paper","volume-title":"DSDP3: Dual scaling algorithm for general positive semidefinite programming","author":"S.J. Benson","year":"2001","unstructured":"S.J. Benson and Y. Ye, DSDP3: Dual scaling algorithm for general positive semidefinite programming, Working paper, Computational Optimization Laboratory, Department of Management Science, University of Iowa, Iowa City (2001)."},{"key":"5098008_CR6","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0166-218X(87)90039-4","volume":"18","author":"W. Cook","year":"1987","unstructured":"W. Cook, C.R. Coullard and G. Turan, On the complexity of cutting plane proofs, Discrete Applied Mathematics 18 (1987) 25\u201338.","journal-title":"Discrete Applied Mathematics"},{"key":"5098008_CR7","series-title":"Working paper","volume-title":"Solving sparse semidefinite programs using the dual scaling algorithm with an iterative solver","author":"C. Choi","year":"2000","unstructured":"C. Choi and Y. Ye, Solving sparse semidefinite programs using the dual scaling algorithm with an iterative solver, Working paper, Computational Optimization Laboratory, Department of Management Science, University of Iowa, Iowa City (2000)."},{"key":"5098008_CR8","first-page":"213","volume":"20","author":"E. de Klerk","year":"1997","unstructured":"E. de Klerk, C. Roos and T. Terlaky, Initialization in semidefinite programming via a self-dual, skew-symmetric embedding, OR Letters 20 (1997) 213\u2013221.","journal-title":"OR Letters"},{"key":"5098008_CR9","doi-asserted-by":"crossref","unstructured":"E. de Klerk, C. Roos and T. Terlaky, Infeasible-start semidefinite programming algorithms via selfdual embeddings, in: Topics in Semidefinite and Interior-Point Methods, eds. P.M. Pardalos and H. Wolkowicz, Fields Institute Communications Series, Vol. 18 (American Mathematical Society, 1998) pp. 215\u2013236.","DOI":"10.1090\/fic\/018\/15"},{"key":"5098008_CR10","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1023\/A:1006362203438","volume":"24","author":"E. de Klerk","year":"2000","unstructured":"E. de Klerk, H. van Maaren and J.P. Warners, Relaxations of the satisfiability problem using semidefinite programming, Journal of Automated Reasoning 24 (2000) 37\u201365.","journal-title":"Journal of Automated Reasoning"},{"issue":"6","key":"5098008_CR11","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"M.X. Goemans and D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM 42(6) (1995) 1115\u20131145.","journal-title":"Journal of the ACM"},{"key":"5098008_CR12","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0304-3975(85)90144-6","volume":"39","author":"A. Haken","year":"1985","unstructured":"A. Haken, The intractability of resolution, Theoretical Computer Science 39 (1985) 297\u2013308.","journal-title":"Theoretical Computer Science"},{"key":"5098008_CR13","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1006\/jagm.2001.1162","volume":"40","author":"E. Halperin","year":"2001","unstructured":"E. Halperin and U. Zwick, Approximation algorithms for MAX 4-SAT and rounding procedures for semidefinite programs, Journal of Algorithms 40 (2001) 184\u2013211.","journal-title":"Journal of Algorithms"},{"issue":"2","key":"5098008_CR14","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1093\/qmath\/39.4.463","volume":"39","author":"W.-Y. Hsiang","year":"1988","unstructured":"W.-Y. Hsiang, On infinitesimal symmetrization and volume formula for spherical or hyperbolic tetrahedrons, The Quarterly Journal of Mathematics. Oxford 39(2) (1988) pp. 463\u2013468.","journal-title":"The Quarterly Journal of Mathematics"},{"key":"5098008_CR15","doi-asserted-by":"crossref","unstructured":"H. Karloff and U. Zwick, A 7\/8-approximation algorithm for MAX 3SAT?, in: Proc. 38th FOCS (1997) 406\u2013415.","DOI":"10.1109\/SFCS.1997.646129"},{"key":"5098008_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"L. Lov\u00e1sz, On the Shannon capacity of a graph, IEEE Transactions on Information Theory 25 (1979) 1\u20137.","journal-title":"IEEE Transactions on Information Theory"},{"key":"5098008_CR17","doi-asserted-by":"crossref","unstructured":"S. Mahajan and H. Ramesh, Derandomizing semidefinite programming based approximation algorithms, in: Proc. of the 36th Annual IEEE Symposium on Foundations of Computer Science (1995) pp. 162\u2013169.","DOI":"10.1109\/SFCS.1995.492473"},{"key":"5098008_CR18","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R. Monasson","year":"1999","unstructured":"R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman and L. Troyansky, Determining computational complexity from characteristic 'phase transitions', Nature 400 (1999) 133\u2013137.","journal-title":"Nature"},{"key":"5098008_CR19","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G","volume":"15","author":"R. Monasson","year":"1999","unstructured":"R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman and L. Troyansky, 2 + P-SAT: relation of typical-case complexity to the nature of the phase transition, Random Structure and Algorithms 15 (1999) 414\u2013435.","journal-title":"Random Structure and Algorithms"},{"key":"5098008_CR20","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1080\/10556789908805766","volume":"11-12","author":"J.F. Sturm","year":"1999","unstructured":"J.F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optimization Methods and Software 11-12 (1999) 625\u2013653.","journal-title":"Optimization Methods and Software"},{"key":"5098008_CR21","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/S0166-218X(99)00041-4","volume":"96-97","author":"H. Van Maaren","year":"1999","unstructured":"H. Van Maaren, Elliptic approximations of propositional formulae, Discrete Applied Mathematics 96-97 (1999) 223\u2013244.","journal-title":"Discrete Applied Mathematics"},{"key":"5098008_CR22","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0166-218X(99)00135-3","volume":"99","author":"J.P. Warners","year":"2000","unstructured":"J.P. Warners and H. Van Maaren, Recognition of tractable satisfiability problems through balanced polynomial representations, Discrete Applied Mathematics 99 (2000) 229\u2013244.","journal-title":"Discrete Applied Mathematics"},{"key":"5098008_CR23","doi-asserted-by":"crossref","unstructured":"U. Zwick, Outward rotations: a new tool for rounding solutions of semidefinite programming relaxations, with applications toMAX CUT and other problems, in: Proc. 31st STOC (1999) pp. 679\u2013687.","DOI":"10.1145\/301250.301431"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1021208315170.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1021208315170\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1021208315170.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T05:33:44Z","timestamp":1747546424000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1021208315170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,3]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2003,3]]}},"alternative-id":["5098008"],"URL":"https:\/\/doi.org\/10.1023\/a:1021208315170","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[2003,3]]}}}