{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:46:38Z","timestamp":1725543998198},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540343066"},{"type":"electronic","value":"9783540343073"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11757375_10","type":"book-chapter","created":{"date-parts":[[2006,5,19]],"date-time":"2006-05-19T03:59:15Z","timestamp":1148011155000},"page":"104-118","source":"Crossref","is-referenced-by-count":5,"title":["The Power of Semidefinite Programming Relaxations for MAX-SAT"],"prefix":"10.1007","author":[{"given":"Carla P.","family":"Gomes","sequence":"first","affiliation":[]},{"given":"Willem-Jan","family":"van Hoeve","sequence":"additional","affiliation":[]},{"given":"Lucian","family":"Leahu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Hooker, J.N., Fedjiki, C.: Branch-and-cut solution of inference problems in propositional logic. Annals of Math. and Artificial Intelligence\u00a01 (1990)","DOI":"10.1007\/BF01531074"},{"key":"10_CR2","unstructured":"Warners, J.: Nonlinear approaches to satisfiability problems. PhD thesis, Technische Universiteit Eindhoven (1999)"},{"issue":"1-2","key":"10_CR3","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.artint.2005.01.004","volume":"164","author":"Z. Xing","year":"2005","unstructured":"Xing, Z., Zhang, W.: Maxsolver: An efficient exact algorithm for (weighted) maximum satisfiability. Artificial Intelligence\u00a0164(1-2), 47\u201380 (2005)","journal-title":"Artificial Intelligence"},{"key":"10_CR4","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1090\/dimacs\/035\/13","volume":"35","author":"S. Joy","year":"1997","unstructured":"Joy, S., Mitchell, J., Borchers, B.: A branch and cut algorithm for MAX-SAT and weighted MAX-SAT. Satisfiability Problem: Theory and Applications\u00a035, 519\u2013536 (1997)","journal-title":"Satisfiability Problem: Theory and Applications"},{"issue":"1","key":"10_CR5","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1137\/0805002","volume":"5","author":"F. Alizadeh","year":"1995","unstructured":"Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization\u00a05(1), 13\u201351 (1995)","journal-title":"SIAM Journal on Optimization"},{"key":"10_CR6","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/978-1-4615-4381-7_12","volume-title":"Handbook of Semidefinite Programming","author":"M. Goemans","year":"2000","unstructured":"Goemans, M., Rendl, F.: Combinatorial Optimization. In: Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.) Handbook of Semidefinite Programming, pp. 343\u2013360. Kluwer, Dordrecht (2000)"},{"key":"10_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. John Wiley & Sons, Chichester (1988)"},{"issue":"6","key":"10_CR8","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.: Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Journal of the ACM\u00a042(6), 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Hochbaum, D.S.: (Editor) Approximation algorithms for NP-Hard problems. PWS Publishing Company (1997)","DOI":"10.1145\/261342.571216"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Feige, U., Goemans, M.: Approximating the value of two prover proof systems, with applications to max2sat and max dicut. In: Proceedings of the 3rd Israel Symposium on Theory of Computing and Systems (1995)","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"10_CR11","volume-title":"Computers and Intractibility","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractibility. Freeman, New York (1979)"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V., Reed, B.: Mike gets some (the odds are on his side). In: 33th Annual Symposium of Foundations of Computer Science, pp. 620\u2013627 (1992)","DOI":"10.1109\/SFCS.1992.267789"},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/3-540-47867-1_6","volume-title":"Integer Programming and Combinatorial Optimization","author":"M. Lewin","year":"2002","unstructured":"Lewin, M., Livnat, D., Zwick, U.: Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol.\u00a02337, pp. 67\u201382. Springer, Heidelberg (2002)"},{"key":"10_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3233\/SAT190001","volume":"1","author":"M. Anjos","year":"2005","unstructured":"Anjos, M.: Semidefinite optimization approaches for satisfiability and maximum-satisfiability problems. Journal on Satisfiability, Boolean Modeling and Computation\u00a01, 1\u201347 (2005)","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"de Klerk, E., van Maaren, H.: On semidefinite programming relaxation of 2+p-sat. Annals of Math. and Artificial Intelligence\u00a037 (2003)","DOI":"10.1023\/A:1021208315170"},{"key":"10_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"10_CR17","unstructured":"Selman, B.: Mwff - a program for generating random MAX k-SAT instances (1993)"},{"issue":"1","key":"10_CR18","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1080\/10556789908805765","volume":"11","author":"B. Borchers","year":"1999","unstructured":"Borchers, B.: A C Library for Semidefinite Programming. Optimization Methods and Software\u00a011(1), 613\u2013623 (1999), http:\/\/www.nmt.edu\/~borchers\/csdp.html","journal-title":"Optimization Methods and Software"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Selman, B., Kautz, H., Cohen, B.: Local search strategies for satisfiability testing (1996)","DOI":"10.1090\/dimacs\/026\/25"}],"container-title":["Lecture Notes in Computer Science","Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11757375_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,14]],"date-time":"2020-04-14T19:16:18Z","timestamp":1586891778000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11757375_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540343066","9783540343073"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11757375_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}