{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T22:12:09Z","timestamp":1765231929524},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,7,23]],"date-time":"2011-07-23T00:00:00Z","timestamp":1311379200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,9]]},"DOI":"10.1007\/s00453-011-9550-1","type":"journal-article","created":{"date-parts":[[2011,7,22]],"date-time":"2011-07-22T15:11:27Z","timestamp":1311347487000},"page":"56-68","source":"Crossref","is-referenced-by-count":9,"title":["A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and Its Algorithmic Applications"],"prefix":"10.1007","volume":"64","author":[{"given":"Robert","family":"Crowston","sequence":"first","affiliation":[]},{"given":"Gregory","family":"Gutin","sequence":"additional","affiliation":[]},{"given":"Mark","family":"Jones","sequence":"additional","affiliation":[]},{"given":"Anders","family":"Yeo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,7,23]]},"reference":[{"key":"9550_CR1","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1007\/11847250_24","volume-title":"Proc. IWPEC 2006","author":"F.N. Abu-Khzam","year":"2006","unstructured":"Abu-Khzam, F.N., Fernau, H.: Kernels: annotated, proper and induced. In: Proc. IWPEC 2006. Lect. Notes Comput. Sci., vol. 4169, pp. 264\u2013275 (2006)"},{"issue":"2","key":"9550_CR2","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/0097-3165(86)90060-9","volume":"43","author":"R. Aharoni","year":"1986","unstructured":"Aharoni, R., Linial, N.: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas. J. Comb. Theory, Ser. A 43(2), 196\u2013204 (1986)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"9550_CR3","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/978-3-642-03073-4_13","volume-title":"Proc. CiE 2009","author":"Y. Chen","year":"2009","unstructured":"Chen, Y., Flum, J., M\u00fcller, M.: Lower bounds for kernelizations and other preprocessing procedures. In: Proc. CiE 2009. Lect. Notes Comput. Sci., vol.\u00a05635. pp. 118\u2013128 (2009)"},{"key":"9550_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"9550_CR5","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"issue":"1","key":"9550_CR6","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1016\/S0304-3975(01)00337-1","volume":"289","author":"H. Fleischner","year":"2002","unstructured":"Fleischner, H., Kullmann, O., Szeider, S.: Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference. Theor. Comput. Sci. 289(1), 503\u2013516 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9550_CR7","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1007\/978-3-642-22953-4_12","volume-title":"Proc. FCT 2011","author":"G. Gutin","year":"2011","unstructured":"Gutin, G., Jones, M., Yeo, A.: A new bound for 3-satisfiable MaxSat and its algorithmic application. In: Proc. FCT 2011. Lect. Notes Comput. Sci., vol. 6914, pp. 138\u2013147 (2011)"},{"key":"9550_CR8","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0304-3975(85)90166-5","volume":"40","author":"M.A. Huang","year":"1985","unstructured":"Huang, M.A., Lieberherr, K.J.: Implications of forbidden structures for extremal algorithmic problems. Theor. Comput. Sci. 40, 195\u2013210 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"9550_CR9","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1016\/j.endm.2007.07.077","volume":"29","author":"C. K\u00e4ppeli","year":"2007","unstructured":"K\u00e4ppeli, C., Scheder, D.: Partial satisfaction of k-satisfiable formulas. Electron. Notes Discrete Math. 29, 497\u2013501 (2007)","journal-title":"Electron. Notes Discrete Math."},{"key":"9550_CR10","first-page":"330","volume-title":"Proc. SODA 2004","author":"D. Kr\u00e1l","year":"2004","unstructured":"Kr\u00e1l, D.: Locally satisfiable formulas. In: Proc. SODA 2004, pp. 330\u2013339 (2004)"},{"issue":"2","key":"9550_CR11","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1145\/322248.322260","volume":"28","author":"K.J. Lieberherr","year":"1981","unstructured":"Lieberherr, K.J., Specker, E.: Complexity of partial satisfaction. J. ACM 28(2), 411\u2013421 (1981)","journal-title":"J. ACM"},{"key":"9550_CR12","unstructured":"Lieberherr, K.J., Specker, E.: Complexity of partial satisfaction, II. Tech. Report 293, Dept. of EECS, Princeton Univ. (1982)"},{"key":"9550_CR13","unstructured":"Lokshtanov, D.: New methods in parameterized algorithms and complexity. PhD thesis, Bergen (April 2009)"},{"issue":"2","key":"9550_CR14","doi-asserted-by":"crossref","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"},{"key":"9550_CR15","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","volume":"10","author":"B. Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Solving satisfiability in less than 2 n steps. Discrete Appl. Math. 10, 287\u2013295 (1985)","journal-title":"Discrete Appl. Math."},{"key":"9550_CR16","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)"},{"issue":"4","key":"9550_CR17","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1016\/j.jcss.2004.04.009","volume":"69","author":"S. Szeider","year":"2004","unstructured":"Szeider, S.: Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. J. Comput. Syst. Sci. 69(4), 656\u2013674 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9550_CR18","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1137\/S0895480197326528","volume":"17","author":"L. Trevisan","year":"2004","unstructured":"Trevisan, L.: On local versus global satisfiability. SIAM J. Discrete Math. 17(4), 541\u2013547 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"9550_CR19","doi-asserted-by":"crossref","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, 475\u2013502 (1994)","journal-title":"J. Algorithms"},{"key":"9550_CR20","volume-title":"Introduction to Graph Theory","author":"D.B. West","year":"2001","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, New York (2001)","edition":"2"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9550-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9550-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9550-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:08Z","timestamp":1559123108000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9550-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7,23]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["9550"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9550-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,7,23]]}}}