{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T10:14:24Z","timestamp":1752228864908},"publisher-location":"Berlin, Heidelberg","reference-count":8,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614227"},{"type":"electronic","value":"9783540685296"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_124","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:36:55Z","timestamp":1330292215000},"page":"100-111","source":"Crossref","is-referenced-by-count":6,"title":["Approximation algorithms for the maximum satisfiability problem"],"prefix":"10.1007","author":[{"given":"Takao","family":"Asano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takao","family":"Ono","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomio","family":"Hirata","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"U. Feige and Michel X. Goemans, 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, 1995, pp.182\u2013189.","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Michel X. Goemans and David P. Williamson. 878-approximation algorithms for MAX CUT and MAX 2SAT, In Proc. 26th STOC, 1994, pp.422\u2013431.","DOI":"10.1145\/195058.195216"},{"key":"10_CR3","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"M. X. Goemans","year":"1994","unstructured":"Michel X. Goemans and David P. Williamson, New 3\/4-approximation algorithms for the maximum satisfiability problem, SIAM Journal of Disc. Math., 7 (1994), pp.656\u2013666.","journal-title":"SIAM Journal of Disc. Math."},{"key":"10_CR4","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. X. Goemans","year":"1995","unstructured":"Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using seinidefinite programming, In Journal of the ACM, 42 (1995), pp.1115\u20131145.","journal-title":"Journal of the ACM"},{"key":"10_CR5","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. S. Johnson","year":"1974","unstructured":"David S. Johnson, Approximation algorithms for combinatorial problems, Journal of Comput. and Sys. Sci., 9 (1974), pp.256\u2013278.","journal-title":"Journal of Comput. and Sys. Sci."},{"key":"10_CR6","unstructured":"S. Mahajan and H. Ramesh, Correctly derandomizing Geomans and Williamson's MAX CUT algorithm, Unpublished manuscript, 1995"},{"key":"10_CR7","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"11","author":"E. Tardos","year":"1986","unstructured":"E. Tardos, A strongly polynomial algorithm for solving combinatoral linear program, Operations Research, 11 (1986), pp.250\u2013256.","journal-title":"Operations Research"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Mihalis Yannakakis, On the approximation of maximum satisfiability, in Proc. 3rd SODA, 1992, pp.1\u20139 (and also in J. Algorithms, 17 (1994), pp.475\u2013502).","DOI":"10.1006\/jagm.1994.1045"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61422-2_124.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:05:58Z","timestamp":1605647158000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_124"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":8,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_124","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}