乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T03:20:02Z","timestamp":1725852002421},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662495285"},{"type":"electronic","value":"9783662495292"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49529-2_49","type":"book-chapter","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T04:09:41Z","timestamp":1458533381000},"page":"659-671","source":"Crossref","is-referenced-by-count":0,"title":["Simple Approximation Algorithms for Balanced MAX 2SAT"],"prefix":"10.1007","author":[{"given":"Alice","family":"Paul","sequence":"first","affiliation":[]},{"given":"Matthias","family":"Poloczek","sequence":"additional","affiliation":[]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,22]]},"reference":[{"key":"49_CR1","unstructured":"Argelich, J., Li, C.M., Many\u00e0, F., Planes, J.: MAX-SAT 2014: Ninth Max-SAT evaluation. \n www.maxsat.udl.cat\/14\/\n \n . Accessed 9 January 2015"},{"key":"49_CR2","doi-asserted-by":"crossref","unstructured":"Austrin, P.: Balanced MAX 2-SAT might not be the hardest. In: STOC, pp. 189\u2013197 (2007)","DOI":"10.1145\/1250790.1250818"},{"key":"49_CR3","unstructured":"Belov, A., Diepold, D., Heule, M.J., J\u00e4rvisalo, M.: Proceedings of the SAT COMPETITION 2014: solver and benchmark descriptions (2014)"},{"key":"49_CR4","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: A tight linear time (1\/2)-approximation for unconstrained submodular maximization. In: FOCS, pp. 649\u2013658 (2012)","DOI":"10.1109\/FOCS.2012.73"},{"key":"49_CR5","doi-asserted-by":"crossref","unstructured":"Chan, S.O., Lee, J., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. In: FOCS, pp. 350\u2013359 (2013)","DOI":"10.1109\/FOCS.2013.45"},{"key":"49_CR6","unstructured":"Feige, U., Goemans, M.X.: Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT. In: ISTCS, pp. 182\u2013189 (1995)"},{"issue":"4","key":"49_CR7","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"MX Goemans","year":"1994","unstructured":"Goemans, M.X., Williamson, D.P.: New 3\/4-approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math. 7(4), 656\u2013666 (1994)","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"49_CR8","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"issue":"3","key":"49_CR9","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"49_CR10","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1137\/S0097539705447372","volume":"37","author":"S Khot","year":"2007","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnell, R.: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput. 37(1), 319\u2013357 (2007)","journal-title":"SIAM J. Comput."},{"key":"49_CR11","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. 2337, pp. 67\u201382. Springer, Heidelberg (2002)"},{"key":"49_CR12","unstructured":"Matuura, S., Matsui, T.: \n \n \n \n $$0.935$$\n \n \n \n 0.935\n \n \n \n -approximation randomized algorithm for MAX-2SAT and its derandomization. Technical report METR 2001-03, Department of Mathematical Engineering and Physics, the University of Tokyo, Japan (2001)"},{"key":"49_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-642-23719-5_4","volume-title":"Algorithms \u2013 ESA 2011","author":"M Poloczek","year":"2011","unstructured":"Poloczek, M.: Bounds on greedy algorithms for MAX\u00a0SAT. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 37\u201348. Springer, Heidelberg (2011)"},{"key":"49_CR14","unstructured":"Poloczek, M.: Greedy Algorithms for MAX SAT and Maximum Matching: Their Power and Limitations. Ph.D. thesis, Johann Wolfgang Goethe-Universitaet, Frankfurt am Main (2012)"},{"key":"49_CR15","doi-asserted-by":"crossref","unstructured":"Poloczek, M.: An experimental evaluation of fast approximation algorithms for the maximum satisfiability problem (2015) (in preparation)","DOI":"10.1007\/978-3-319-38851-9_17"},{"key":"49_CR16","doi-asserted-by":"crossref","unstructured":"Poloczek, M., Schnitger, G.: Randomized variants of Johnson\u2019s algorithm for MAX SAT. In: SODA, pp. 656\u2013663 (2011)","DOI":"10.1137\/1.9781611973082.51"},{"key":"49_CR17","unstructured":"Poloczek, M., Schnitger, G., Williamson, D.P., van Zuylen, A.: Greedy algorithms for the maximum satisfiability problem: simple algorithms and inapproximability bounds (2015) (in preparation)"},{"key":"49_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1007\/978-3-642-54423-1_52","volume-title":"LATIN 2014: Theoretical Informatics","author":"M Poloczek","year":"2014","unstructured":"Poloczek, M., Williamson, D.P., van Zuylen, A.: On some recent approximation algorithms for MAX SAT. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 598\u2013609. Springer, Heidelberg (2014)"},{"issue":"1","key":"49_CR19","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1137\/14099098X","volume":"29","author":"JA Soto","year":"2015","unstructured":"Soto, J.A.: Improved analysis of a Max-Cut algorithm based on spectral partitioning. SIAM J. Discrete Math. 29(1), 259\u2013268 (2015)","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"49_CR20","doi-asserted-by":"publisher","first-page":"1769","DOI":"10.1137\/090773714","volume":"41","author":"L Trevisan","year":"2012","unstructured":"Trevisan, L.: Max Cut and the smallest eigenvalue. SIAM J. Comput. 41(6), 1769\u20131786 (2012)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"49_CR21","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1006\/jagm.1994.1045","volume":"17","author":"M Yannakakis","year":"1994","unstructured":"Yannakakis, M.: On the approximation of maximum satisfiability. J. Algorithms 17(3), 475\u2013502 (1994)","journal-title":"J. Algorithms"},{"key":"49_CR22","doi-asserted-by":"crossref","unstructured":"van Zuylen, A.: Simpler 3\/4-approximation algorithms for MAX SAT. In: WAOA, pp. 188\u2013197 (2011)","DOI":"10.1007\/978-3-642-29116-6_16"}],"container-title":["Lecture Notes in Computer Science","LATIN 2016: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49529-2_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T16:35:03Z","timestamp":1559406903000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49529-2_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662495285","9783662495292"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49529-2_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}