{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:27:52Z","timestamp":1725600472657},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642226847"},{"type":"electronic","value":"9783642226854"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22685-4_5","type":"book-chapter","created":{"date-parts":[[2011,8,10]],"date-time":"2011-08-10T04:54:39Z","timestamp":1312952079000},"page":"49-61","source":"Crossref","is-referenced-by-count":1,"title":["Tight Bounds on Local Search to Approximate the Maximum Satisfiability Problems"],"prefix":"10.1007","author":[{"given":"Daming","family":"Zhu","sequence":"first","affiliation":[]},{"given":"Shaohan","family":"Ma","sequence":"additional","affiliation":[]},{"given":"Pingping","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","first-page":"151","volume-title":"Proceedings of the 3rd Annual ACM Symposium on Theorey of Computing, Shaker Heights","author":"S.A. Cook","year":"1971","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theorey of Computing, Shaker Heights, Ohio,USA, pp. 151\u2013158. ACM, New York (1971)"},{"issue":"3","key":"5_CR2","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yanakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences\u00a043(3), 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"5_CR3","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences\u00a09(3), 256\u2013278 (1974)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"5_CR4","doi-asserted-by":"publisher","first-page":"622","DOI":"10.1006\/jcss.1998.1612","volume":"58","author":"J. Chen","year":"1999","unstructured":"Chen, J., Friesen, D., Zheng, H.: Tight bound on Johnson\u2019s algorithm for maximum satisfiability. Journal of Computer and System Sciences\u00a058(3), 622\u2013640 (1999)","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR5","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. Journal of Algorithms\u00a017, 475\u2013502 (1994)","journal-title":"Journal of Algorithms"},{"issue":"4","key":"5_CR6","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(4), 656\u2013666 (1994)","journal-title":"Siam Journal on Discrete Mathematics"},{"issue":"6","key":"5_CR7","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 semi-definite programming. Journal of the ACM\u00a042(6), 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1109\/ISTCS.1995.377033","volume-title":"Proceedings of the 3rd Israel Symposium on Theorey and Computing Systems","author":"U. Feige","year":"1995","unstructured":"Feige, U., Goemans, M.X.: Approximating the value of two power proof systems, with applications to Max-2Sat and Max-Dicut. In: Proceedings of the 3rd Israel Symposium on Theorey and Computing Systems, Tel Aviv, Israel, pp. 182\u2013189. IEEE, Washington, DC, USA (1995)"},{"key":"5_CR9","first-page":"617","volume-title":"Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science","author":"L. Trevisan","year":"1996","unstructured":"Trevisan, L., Sorkin, G.B., Sudan, M., Williamson, D.P.: Gadets, approximation, and linear programming. In: Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, Burlington, Vermont, pp. 617\u2013626. IEEE, Washington, DC, USA (1996)"},{"issue":"1","key":"5_CR10","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s004530010035","volume":"28","author":"L. Trevisan","year":"2000","unstructured":"Trevisan, L.: Approximating satisfiable satisfiability problems. Algorithmica\u00a028(1), 145\u2013172 (2000)","journal-title":"Algorithmica"},{"key":"5_CR11","first-page":"406","volume-title":"Proceedings of the 38th IEEE Symposium on Foundations of Computer Science","author":"H. Karloff","year":"1997","unstructured":"Karloff, H., Zwick, U.: A 7\/8-approximation algorithm for Max 3Sat? In: Proceedings of the 38th IEEE Symposium on Foundations of Computer Science, Miami Beach, Florida, pp. 406\u2013415. IEEE, Washington, DC, USA (1997)"},{"issue":"2","key":"5_CR12","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(2), 184\u2013211 (2001)","journal-title":"Journal of Algorithms"},{"key":"5_CR13","first-page":"1","volume-title":"Proceedings of the 28th Annual ACM Symposium on Theorey of Computing","author":"J. Hastad","year":"1997","unstructured":"Hastad, J.: Some optimal inapproximability results. In: Proceedings of the 28th Annual ACM Symposium on Theorey of Computing, El Paso, Texas, pp. 1\u201310. ACM, New York (1997)"},{"issue":"1","key":"5_CR14","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/130836.130837","volume":"3","author":"J. Gu","year":"1992","unstructured":"Gu, J.: Efficient local search for very large-scale satisfiability problems. ACM SIGART Bulletin\u00a03(1), 8\u201312 (1992)","journal-title":"ACM SIGART Bulletin"},{"key":"5_CR15","unstructured":"Selman, B., Levesque, H., Mitchell, D.: A new method for solving hard satisfiability problems. In: Proceedings of the 10th National Conference on Artificial Intelligence, Pasadena, Calefornia, pp. 440\u2013446 (1992)"},{"issue":"1","key":"5_CR16","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0020-0190(92)90029-U","volume":"43","author":"E. Koutsoupias","year":"1992","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: On the greedy algorithm for satisfiability. Information Processing Letters\u00a043(1), 53\u201355 (1992)","journal-title":"Information Processing Letters"},{"issue":"4","key":"5_CR17","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF02241270","volume":"44","author":"P. Hansen","year":"1990","unstructured":"Hansen, P., Jaumard, B.: Algorithms for the maximum satisfiability problem. Computing\u00a044(4), 279\u2013303 (1990)","journal-title":"Computing"},{"key":"5_CR18","unstructured":"Mastrolilli, M., Gambardella, L.M.: Max-2-Sat: How good is tabu search in the worst case? In: Proceedings of AAAI, pp. 173\u2013178 (2004)"},{"key":"5_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/978-3-642-14186-7_19","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2010","author":"D. Pankratov","year":"2010","unstructured":"Pankratov, D., Borodin, A.: On the relative merits of simple local search methods for the MAX-SAT problem. In: Strichman, O., Szeider, S. (eds.) SAT 2010. LNCS, vol.\u00a06175, pp. 223\u2013236. Springer, Heidelberg (2010)"},{"issue":"2","key":"5_CR20","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0166-218X(02)00404-3","volume":"130","author":"E.A. Hirsch","year":"2003","unstructured":"Hirsch, E.A.: Worst Case Study of Local Search for Max-k-Sat. Discrete Applied Mathematics\u00a0130(2), 173\u2013184 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"5_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/11814948_29","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"A.A. Bulatov","year":"2006","unstructured":"Bulatov, A.A., Skvortsov, E.S.: The Efficiency of local search. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol.\u00a04121, pp. 297\u2013310. Springer, Heidelberg (2006)"},{"key":"5_CR22","first-page":"185","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity, pp. 185\u2013188. Addison Wesley, Reading (1994)"},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"Agarwal, A., Charikar, M., Makarychev, K., Makarychev, Y.: $\\sqrt{logn}$ algorithm for Min UnCut, Min 2CNF deletion, and directed cut problems. In: Proceeding of STOC 2005, pp. 573\u2013581 (2005)","DOI":"10.1145\/1060590.1060675"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22685-4_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T19:39:27Z","timestamp":1560454767000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22685-4_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642226847","9783642226854"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22685-4_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}