{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:19:04Z","timestamp":1725664744940},"publisher-location":"Berlin, Heidelberg","reference-count":14,"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_122","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:37:47Z","timestamp":1330292267000},"page":"76-87","source":"Crossref","is-referenced-by-count":5,"title":["Randomized approximation of the constraint satisfaction problem"],"prefix":"10.1007","author":[{"given":"Hoong Chuin","family":"Lau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Osamu","family":"Watanabe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"8_CR1","unstructured":"Noga Alon and Joe Spencer. The Probabilistic Method. Wiley Interscience Ser. Disc. Math. and Optimiz., 1992."},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proc. 33th. IEEE Symp. on Found, of Comp. Sci., pages 2\u201313, 1993.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"8_CR3","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P. Berman","year":"1992","unstructured":"P. Berman and G. Schnitger. On the complexity of approximating the independent set problem. Infor. & Comput., 96:77\u201394, 1992.","journal-title":"Infor. & Comput."},{"key":"8_CR4","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1016\/0097-3165(73)90005-8","volume":"14","author":"P. Erd\u00f6s","year":"1989","unstructured":"P. Erd\u00f6s and L. Selfridge. On a combinatorial game. J. Comb. Theory Series A, 14:298\u2013301, 1989.","journal-title":"J. Comb. Theory Series A"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Uriel Feige and L\u00e1szl\u00f3 Lov\u00e1sz. Two-prover one-round proof systems: Their power and their problems. In Proc. 24th ACM Symp. on Theory of Computing, pages 733\u2013744, 1992.","DOI":"10.1145\/129712.129783"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Michel X. Goemans and David P. Williamson. Approximation algorithms for MAX CUT and MAX 2SAT. In Proc. 26th ACM Symp. on Theory of Computing, pages 422\u2013431, 1994. Full version to appear in J. ACM.","DOI":"10.1145\/195058.195216"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"S. Khanna, R. Motwani, M. Sudan, and U. Vazirani. On syntactic versus computational views of approximability. In Proc. 35th. IEEE Symp. on Found, of Comp. Sci., 1994.","DOI":"10.1109\/SFCS.1994.365712"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"H. C. Lau. Approximation of constraint satisfaction via local search. In Proc. 4th Wrksp. on Algorithms and Data Structures (WADS), pages 461\u2013472. Springer Verlag Lect. Notes Comp. Sci. (955), 1995.","DOI":"10.1007\/3-540-60220-8_85"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"S. Mahajan and H. Ramesh. Derandomizing semidefinite programming based approximation algorithms. In Proc. 36th IEEE Symp. on Found, of Comp. Sci., pages 162\u2013168, 1995.","DOI":"10.1109\/SFCS.1995.492473"},{"key":"8_CR10","volume-title":"Elementary Differential Geometry","author":"B. O'Neill","year":"1966","unstructured":"Barrett O'Neill. Elementary Differential Geometry. Academic Press, New York, 1966."},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"Christos H. Papadimitriou and Mihalis Yaimakakis. Optimization, approximation, and complexity classes. J. Comput. Sys. Sci., 43:425\u2013440, 1991.","journal-title":"J. Comput. Sys. Sci."},{"issue":"4","key":"8_CR12","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"P. Raghavan and C. D. Thompson. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365\u2013374, 1987.","journal-title":"Combinatorica"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Ran Raz. A parallel repetition theorem. In Proc. 27th ACM Symp. on Theory of Computing, pages 447\u2013456, 1995.","DOI":"10.1145\/225058.225181"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Luca Trevisan. Positive linear programming, parallel approximation and PCPs, 1996. Manuscript.","DOI":"10.1007\/3-540-61680-2_47"}],"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_122.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:05:57Z","timestamp":1605647157000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_122","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}