{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:52:57Z","timestamp":1725558777483},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405436"},{"type":"electronic","value":"9783540450771"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45077-1_2","type":"book-chapter","created":{"date-parts":[[2010,6,25]],"date-time":"2010-06-25T20:53:34Z","timestamp":1277499214000},"page":"2-14","source":"Crossref","is-referenced-by-count":1,"title":["An Improved Analysis of Goemans and Williamson\u2019s LP-Relaxation for MAX SAT"],"prefix":"10.1007","author":[{"given":"Takao","family":"Asano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1006\/jagm.2001.1202","volume":"42","author":"T. Asano","year":"2002","unstructured":"Asano, T., Williamson, D.P.: Improved approximation algorithms for MAX SAT. Journal of Algorithms\u00a042, 173\u2013202 (2002)","journal-title":"Journal of Algorithms"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Feige, U., Goemans, M.X.: Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT. In: Proc. 3rd Israel Symposium on Theory of Computing and Systems, pp. 182\u2013189 (1995)","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"2_CR3","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"M.X. Goemans","year":"1994","unstructured":"Goemans, M.X., Williamson, D.P.: New 3\/4-approximation algorithms for the maximum satisfiability problem. SIAM Journal on Discrete Mathematics\u00a07, 656\u2013666 (1994)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"2_CR4","doi-asserted-by":"publisher","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. Journal of the ACM\u00a042, 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. In: Proc. 28th ACM Symposium on the Theory of Computing, pp. 1\u201310 (1997)","DOI":"10.1145\/258533.258536"},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1006\/jagm.2001.1162","volume":"40","author":"E. Halperin","year":"2001","unstructured":"Halperin, E., Zwick, U.: Approximation algorithms for MAX 4-SAT and rounding procedures for semidefinite programs. Journal of Algorithms\u00a040, 184\u2013211 (2001)","journal-title":"Journal of Algorithms"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Zwick, U.: Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems. In: Proc. 31st ACM Symposium on the Theory of Computing, pp. 679\u2013687 (1999)","journal-title":"Journal of Computer and Systems Science"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Karloff, H., Zwick, U.: A 7\/8-approximation algorithm for MAX 3SAT? In: Proc. 38th IEEE Symposium on the Foundations of Computer Science, pp. 406\u2013415 (1997)","DOI":"10.1109\/SFCS.1997.646129"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Zwick, U.: Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems. In: Proc. 31st ACM Symposium on the Theory of Computing, pp. 679\u2013687 (1999)","DOI":"10.1145\/301250.301431"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45077-1_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T03:36:55Z","timestamp":1552621015000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45077-1_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405436","9783540450771"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45077-1_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}