{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T08:11:37Z","timestamp":1743149497434,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030046507"},{"type":"electronic","value":"9783030046514"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-04651-4_20","type":"book-chapter","created":{"date-parts":[[2018,11,15]],"date-time":"2018-11-15T19:56:50Z","timestamp":1542311810000},"page":"299-313","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Upper and Lower Bounds for Different Parameterizations of (n,3)-MAXSAT"],"prefix":"10.1007","author":[{"given":"Tatiana","family":"Belova","sequence":"first","affiliation":[]},{"given":"Ivan","family":"Bliznets","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,11,16]]},"reference":[{"issue":"3","key":"20_CR1","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/s00453-010-9428-7","volume":"61","author":"N Alon","year":"2011","unstructured":"Alon, N., Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: Solving MAX-r-SAT above a tight lower bound. Algorithmica 61(3), 638\u2013655 (2011)","journal-title":"Algorithmica"},{"key":"20_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/3-540-46632-0_26","volume-title":"Algorithms and Computation","author":"N Bansal","year":"1999","unstructured":"Bansal, N., Raman, V.: Upper bounds for MaxSat: further improved. ISAAC 1999. LNCS, vol. 1741, pp. 247\u2013258. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-46632-0_26"},{"issue":"3","key":"20_CR3","doi-asserted-by":"publisher","first-page":"1401","DOI":"10.1137\/15M1039584","volume":"30","author":"M Basavaraju","year":"2016","unstructured":"Basavaraju, M., Francis, M.C., Ramanujan, M., Saurabh, S.: Partially polynomial kernels for set cover and test cover. SIAM J. Discrete Math. 30(3), 1401\u20131423 (2016)","journal-title":"SIAM J. Discrete Math."},{"key":"20_CR4","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/264216.264220","volume":"2","author":"R Battiti","year":"1997","unstructured":"Battiti, R., Protasi, M.: Reactive search, a history-sensitive heuristic for MAX-SAT. J. Exp. Algorithmics (JEA) 2, 2 (1997)","journal-title":"J. Exp. Algorithmics (JEA)"},{"unstructured":"Berg, J., Hyttinen, A., J\u00e4rvisalo, M.: Applications of MaxSAT in data analysis. Pragmatics of SAT (2015)","key":"20_CR5"},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-642-33293-7_6","volume-title":"Parameterized and Exact Computation","author":"I Bliznets","year":"2012","unstructured":"Bliznets, I., Golovnev, A.: A new algorithm for parameterized MAX-SAT. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol. 7535, pp. 37\u201348. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33293-7_6"},{"issue":"1","key":"20_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10958-012-1101-z","volume":"188","author":"IA Bliznets","year":"2013","unstructured":"Bliznets, I.A.: A new upper bound for (n, 3)-MAX-SAT. J. Math. Sci. 188(1), 1\u20136 (2013)","journal-title":"J. Math. Sci."},{"issue":"1\u20133","key":"20_CR8","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.dam.2003.03.002","volume":"142","author":"J Chen","year":"2004","unstructured":"Chen, J., Kanj, I.A.: Improved exact algorithms for MAX-SAT. Discrete Appl. Math. 142(1\u20133), 17\u201327 (2004)","journal-title":"Discrete Appl. Math."},{"key":"20_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/978-3-319-21840-3_15","volume-title":"Algorithms and Data Structures","author":"J Chen","year":"2015","unstructured":"Chen, J., Xu, C., Wang, J.: Dealing with 4-variables by resolution: an improved MaxSAT algorithm. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 178\u2013188. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21840-3_15"},{"issue":"3","key":"20_CR10","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1007\/s00453-012-9697-4","volume":"68","author":"R Crowston","year":"2014","unstructured":"Crowston, R., Gutin, G., Jones, M., Raman, V., Saurabh, S., Yeo, A.: Fixed-parameter tractability of satisfying beyond the number of variables. Algorithmica 68(3), 739\u2013757 (2014)","journal-title":"Algorithmica"},{"issue":"3","key":"20_CR11","doi-asserted-by":"publisher","first-page":"734","DOI":"10.1007\/s00453-014-9870-z","volume":"72","author":"R Crowston","year":"2015","unstructured":"Crowston, R., Jones, M., Mnich, M.: Max-Cut parameterized above the edwards-erd\u0151s bound. Algorithmica 72(3), 734\u2013757 (2015)","journal-title":"Algorithmica"},{"key":"20_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-16533-7"},{"issue":"2","key":"20_CR13","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/s00224-010-9262-y","volume":"48","author":"G Gutin","year":"2011","unstructured":"Gutin, G., Kim, E.J., Lampis, M., Mitsou, V.: Vertex cover problem parameterized above and below tight bounds. Theory Comput. Syst. 48(2), 402\u2013410 (2011)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"20_CR14","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s00224-007-1330-6","volume":"41","author":"G Gutin","year":"2007","unstructured":"Gutin, G., Rafiey, A., Szeider, S., Yeo, A.: The linear arrangement problem parameterized above guaranteed value. Theory Comput. Syst. 41(3), 521\u2013538 (2007)","journal-title":"Theory Comput. Syst."},{"doi-asserted-by":"crossref","unstructured":"Kojevnikov, A., Kulikov, A.S.: A new approach to proving upper bounds for MAX-2-SAT. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 11\u201317. Society for Industrial and Applied Mathematics (2006)","key":"20_CR15","DOI":"10.1145\/1109557.1109559"},{"issue":"2","key":"20_CR16","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1515\/DMA.2009.009","volume":"19","author":"AS Kulikov","year":"2009","unstructured":"Kulikov, A.S., Kutskov, K.: New upper bounds for the problem of maximal satisfiability. Discrete Math. Appl. 19(2), 155\u2013172 (2009)","journal-title":"Discrete Math. Appl."},{"key":"20_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/978-3-319-71147-8_7","volume-title":"Combinatorial Optimization and Applications","author":"W Li","year":"2017","unstructured":"Li, W., Xu, C., Wang, J., Yang, Y.: An improved branching algorithm for (n,\u00a03)-MaxSAT based on refined observations. In: Gao, X., Du, H., Han, M. (eds.) COCOA 2017 Part II. LNCS, vol. 10628, pp. 94\u2013108. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-71147-8_7"},{"issue":"6","key":"20_CR18","doi-asserted-by":"publisher","first-page":"S5","DOI":"10.1186\/1471-2164-13-S6-S5","volume":"13","author":"PCK Lin","year":"2012","unstructured":"Lin, P.C.K., Khatri, S.P.: Application of MAX-SAT-based atpg to optimal cancer therapy design. BMC Genomics 13(6), S5 (2012)","journal-title":"BMC Genomics"},{"key":"20_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-319-90530-3_21","volume-title":"Computer Science \u2013 Theory and Applications","author":"J Madathil","year":"2018","unstructured":"Madathil, J., Saurabh, S., Zehavi, M.: Max-Cut Above Spanning Tree is fixed-parameter tractable. In: Fomin, F.V., Podolskii, V.V. (eds.) CSR 2018. LNCS, vol. 10846, pp. 244\u2013256. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-90530-3_21"},{"issue":"2","key":"20_CR20","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms 31(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"issue":"1","key":"20_CR21","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1006\/jagm.2000.1075","volume":"36","author":"R Niedermeier","year":"2000","unstructured":"Niedermeier, R., Rossmanith, P.: New upper bounds for maximum satisfiability. J. Algorithms 36(1), 63\u201388 (2000)","journal-title":"J. Algorithms"},{"issue":"3","key":"20_CR22","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1137\/15M1053369","volume":"46","author":"M Poloczek","year":"2017","unstructured":"Poloczek, M., Schnitger, G., Williamson, D.P., Van Zuylen, A.: Greedy algorithms for the maximum satisfiability problem: simple algorithms and inapproximability bounds. SIAM J. Comput. 46(3), 1029\u20131061 (2017)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"20_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(97)00223-8","volume":"65","author":"V Raman","year":"1998","unstructured":"Raman, V., Ravikumar, B., Rao, S.S.: A simplified NP-complete MAXSAT problem. Inf. Processing Letters 65(1), 1\u20136 (1998)","journal-title":"Inf. Processing Letters"},{"unstructured":"Walter, R., Zengler, C., K\u00fcchlin, W.: Applications of MAXSAT in automotive configuration. In: Configuration Workshop, vol. 1, p. 21 (2013)","key":"20_CR24"},{"unstructured":"Xu, C., Chen, J., Wang, J.: Resolution and linear CNF formulas: improved (n, 3)-MaxSAT algorithms. Theor. Comput. Sci. (2016)","key":"20_CR25"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-04651-4_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T15:49:21Z","timestamp":1710344961000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-04651-4_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030046507","9783030046514"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-04651-4_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"16 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Atlanta, GA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spacl.kennesaw.edu\/cocoa2018\/cfp.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}