{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:52:01Z","timestamp":1725486721489},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679967"},{"type":"electronic","value":"9783540444367"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44436-x_16","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T05:33:14Z","timestamp":1182144794000},"page":"155-166","source":"Crossref","is-referenced-by-count":7,"title":["Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses"],"prefix":"10.1007","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,3]]},"reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/S0020-0190(98)00021-0","volume":"65","author":"G. Andersson","year":"1998","unstructured":"G. Andersson and L. Engebretsen. Better approximation algorithms for Set Splitting and Not-All-Equal Sat. Information Processing Letters, 65:305\u2013311, 1998.","journal-title":"Information Processing Letters"},{"issue":"3","key":"16_CR2","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M. Bellare","year":"1998","unstructured":"M. Bellare, O. Goldreich and M. Sudan. Free bits, PCP\u2019s and non-approximability-towards tight results. SIAM Journal on Computing, 27(3):804\u2013915, 1998. Preliminary version in Proc. of FOCS\u201995.","journal-title":"SIAM Journal on Computing"},{"key":"16_CR3","unstructured":"P. Crescenzi, R. Silvestri and L. Trevisan. To weight or not to weight: Where is the question? Proc. of 4th Israel Symposium on Theory of Computing and Systems, pp. 68\u201377, 1996."},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"U. Feige and M. Goemans. Approximating the value of two prover proof systems, with applications to MAX-2SAT and MAX-DICUT. Proc. of the 3rd Israel Symposium on Theory and Computing Systems, Tel Aviv, pp. 182\u2013189, 1995.","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. Goemans","year":"1995","unstructured":"M. Goemans and D. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42:1115\u20131145, 1995.","journal-title":"Journal of the ACM"},{"key":"16_CR6","unstructured":"V. Guruswami. The approximability of set splitting problems and satisfiability problems with no mixed clauses. ECCC Technical Report TR-99-043, 1999."},{"key":"16_CR7","unstructured":"V. Guruswami. Query-efficient Checking of Proofs and Improved PCP Characterizations of NP. S.M Thesis, MIT, May 1999."},{"key":"16_CR8","unstructured":"V. Guruswami, D. Lewin, M. Sudan and L. Trevisan. A tight characterization of NP with 3 query PCPs. ECCC Technical Report TR98-034, 1998. Preliminary Version in Proc. of FOCS\u201998."},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad Some optimal inapproximability results. ECCC Technical Report TR97-37, 1997. Preliminary version in Proc. of STOC\u201997.","DOI":"10.1145\/258533.258536"},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0020-0190(96)00046-4","volume":"58","author":"V. Kann","year":"1996","unstructured":"V. Kann, J. Lagergren and A. Panconesi. Approximability of maximum splitting of k-sets and some other APX-complete problems. Information Processing Letters, 58:105\u2013110, 1996.","journal-title":"Information Processing Letters"},{"key":"16_CR11","unstructured":"H. Karlo. and U. Zwick. A (7\/8-\u03b5)-approximation algorithm for MAX 3SAT? In Proceedings of the 38th FOCS, 1997."},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"S. Khanna, M. Sudan and D. Williamson. A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction. Proc. of the 29th STOC, 1997.","DOI":"10.1145\/258533.258538"},{"key":"16_CR13","unstructured":"L. Lov\u00e1sz. Coverings and colorings of hypergraphs. Proc. 4th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, pp. 3\u201312, Utilitas Mathematica Publishing, Winnipeg, 1973."},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E. Petrank","year":"1994","unstructured":"E. Petrank. The hardness of approximation: Gap location. Computational Complexity, 4:133\u2013157, 1994.","journal-title":"Computational Complexity"},{"issue":"3","key":"16_CR15","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"R. Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763\u2013803, 1998. Preliminary version in Proc. of STOC\u201995.","journal-title":"SIAM Journal on Computing"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"L. Trevisan, G. Sorkin, M. Sudan and D. Williamson. Gadgets, approximation and linear programming. Proceedings of the 37th FOCS, pp. 517\u2013626, 1996.","DOI":"10.1109\/SFCS.1996.548521"},{"key":"16_CR17","unstructured":"U. Zwick. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, 1998."},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"U. Zwick. Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems. In Proceedings of STOC\u201999.","DOI":"10.1145\/301250.301431"}],"container-title":["Lecture Notes in Computer Science","Approximation Algorithms for Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44436-X_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T23:55:06Z","timestamp":1556495706000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44436-X_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679967","9783540444367"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-44436-x_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}