{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:11Z","timestamp":1759639091286},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"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-23719-5_28","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:14:33Z","timestamp":1314710073000},"page":"323-334","source":"Crossref","is-referenced-by-count":5,"title":["Submodular Max-SAT"],"prefix":"10.1007","author":[{"given":"Yossi","family":"Azar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iftah","family":"Gamzu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ran","family":"Roth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Asano, T.: Approximation algorithms for max sat: Yannakakis vs. goemans-williamson. In: Proceedings 5th Israel Symposium on Theory of Computing and Systems, pp. 24\u201337 (1997)","DOI":"10.1109\/ISTCS.1997.595154"},{"issue":"3","key":"28_CR2","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/j.tcs.2005.11.030","volume":"354","author":"T. Asano","year":"2006","unstructured":"Asano, T.: An improved analysis of goemans and williamson\u2019s lp-relaxation for max sat. Theor. Comput. Sci.\u00a0354(3), 339\u2013353 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"28_CR3","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1006\/jagm.2001.1202","volume":"42","author":"T. Asano","year":"2002","unstructured":"Asano, T., Williamson, D.P.: Improved approximation algorithms for max sat. J. Algorithms\u00a042(1), 173\u2013202 (2002)","journal-title":"J. Algorithms"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. In: SICOMP (2010)","DOI":"10.1137\/080733991"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Dependent randomized rounding via exchange properties of combinatorial structures. In: Proceedings 51st FOCS (2010)","DOI":"10.1109\/FOCS.2010.60"},{"issue":"3","key":"28_CR6","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.K., Zheng, H.: Tight bound on johnson\u2019s algorithm for maximum satisfiability. J. Comput. Syst. Sci.\u00a058(3), 622\u2013640 (1999)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"28_CR7","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1002\/rsa.20015","volume":"24","author":"D. Coppersmith","year":"2004","unstructured":"Coppersmith, D., Gamarnik, D., Hajiaghayi, M.T., Sorkin, G.B.: Random max sat, random max cut, and their phase transitions. Random Struct. Algorithms\u00a024(4), 502\u2013545 (2004)","journal-title":"Random Struct. Algorithms"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Schapira, M.: An improved approximation algorithm for combinatorial auctions with submodular bidders. In: Proceedings of 17th SODA, pp. 1064\u20131073 (2006)","DOI":"10.1145\/1109557.1109675"},{"issue":"4","key":"28_CR9","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.ipl.2004.08.001","volume":"92","author":"L. Engebretsen","year":"2004","unstructured":"Engebretsen, L.: Simplified tight analysis of johnson\u2019s algorithm. Inf. Process. Lett.\u00a092(4), 207\u2013210 (2004)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"28_CR10","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"28_CR11","unstructured":"Feldman, M., Naor, J., Schwartz, R.: Personal Communication (2011)"},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Williamson, D.P.: 878-Approximation algorithms for max cut and max 2sat. In: Proceedings 26th STOC, pp. 422\u2013431 (1994)","DOI":"10.1145\/195058.195216"},{"issue":"4","key":"28_CR13","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 J. Discrete Math.\u00a07(4), 656\u2013666 (1994)","journal-title":"SIAM J. Discrete Math."},{"key":"28_CR14","unstructured":"Goundan, P.R., Schulz, A.S.: Revisiting the greedy approach to submodular set function maximization (2007) (manuscript)"},{"issue":"4","key":"28_CR15","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"issue":"3","key":"28_CR16","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. J. Comput. Syst. Sci.\u00a09(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"Karloff, H.J., Zwick, U.: A 7\/8-approximation algorithm for max 3sat? In: Proceedings 38th FOCS, pp. 406\u2013415 (1997)","DOI":"10.1109\/SFCS.1997.646129"},{"key":"28_CR18","doi-asserted-by":"crossref","unstructured":"Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular set functions subject to multiple linear constraints. In: Proceedings 20th SODA, pp. 545\u2013554 (2009)","DOI":"10.1137\/1.9781611973068.60"},{"key":"28_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-642-03685-9_19","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"J. Lee","year":"2009","unstructured":"Lee, J., Sviridenko, M., Vondr\u00e1k, J.: Submodular maximization over multiple matroids via generalized exchange properties. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol.\u00a05687, pp. 244\u2013257. Springer, Heidelberg (2009)"},{"key":"28_CR20","doi-asserted-by":"crossref","unstructured":"Mirrokni, V.S., Schapira, M., Vondr\u00e1k, J.: Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In: Proceedings 9th EC 2008, pp. 70\u201377 (2008)","DOI":"10.1145\/1386790.1386805"},{"key":"28_CR21","doi-asserted-by":"crossref","unstructured":"Moshkovitz, D., Raz, R.: Two-query pcp with subconstant error. J. ACM, 57(5) (2010)","DOI":"10.1145\/1754399.1754402"},{"issue":"3","key":"28_CR22","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"G.L. Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Operations Research\u00a03(3), 177\u2013188 (1978)","journal-title":"Math. Operations Research"},{"key":"28_CR23","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G.L. Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions i. Mathematical Programming\u00a014, 265\u2013294 (1978)","journal-title":"Mathematical Programming"},{"key":"28_CR24","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"},{"issue":"1","key":"28_CR25","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M. Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett.\u00a032(1), 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"28_CR26","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1287\/moor.7.3.410","volume":"7","author":"L.A. Wolsey","year":"1982","unstructured":"Wolsey, L.A.: Maximising real-valued submodular functions: Primal and dual heuristics for location problems. Math. Operations Research\u00a07(3), 410\u2013425 (1982)","journal-title":"Math. Operations Research"},{"issue":"3","key":"28_CR27","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\u00a017(3), 475\u2013502 (1994)","journal-title":"J. Algorithms"},{"key":"28_CR28","doi-asserted-by":"crossref","unstructured":"Zwick, U.: Outward rotations: A tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems. In: Proceedings of 31st STOC, pp. 679\u2013687 (1999)","DOI":"10.1145\/301250.301431"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T16:08:59Z","timestamp":1560528539000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}