{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,22]],"date-time":"2026-02-22T16:54:26Z","timestamp":1771779266694,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2010,7,17]],"date-time":"2010-07-17T00:00:00Z","timestamp":1279324800000},"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":[[2011,11]]},"DOI":"10.1007\/s00453-010-9428-7","type":"journal-article","created":{"date-parts":[[2010,7,16]],"date-time":"2010-07-16T14:41:59Z","timestamp":1279291319000},"page":"638-655","source":"Crossref","is-referenced-by-count":58,"title":["Solving MAX-r-SAT Above a Tight Lower Bound"],"prefix":"10.1007","volume":"61","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]},{"given":"Gregory","family":"Gutin","sequence":"additional","affiliation":[]},{"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]},{"given":"Anders","family":"Yeo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,7,17]]},"reference":[{"key":"9428_CR1","doi-asserted-by":"crossref","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 3rd edn. Wiley, New York (2008)","edition":"3"},{"key":"9428_CR2","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/j.jalgor.2003.09.003","volume":"50","author":"N. Alon","year":"2004","unstructured":"Alon, N., Gutin, G., Krivelevich, M.: Algorithms with large domination ratio. J. Algorithms 50, 118\u2013131 (2004)","journal-title":"J. Algorithms"},{"issue":"3","key":"9428_CR3","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inf. Process. Lett. 8(3), 121\u2013123 (1979)","journal-title":"Inf. Process. Lett."},{"key":"9428_CR4","first-page":"258","volume":"247","author":"C. Berge","year":"1958","unstructured":"Berge, C.: Sur le couplage maximum d\u2019un graphe. C. R. Acad. Sci. Paris 247, 258\u2013259 (1958)","journal-title":"C. R. Acad. Sci. Paris"},{"key":"9428_CR5","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/978-3-642-11269-0_2","volume-title":"Proceedings of IWPEC 2009","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L.: Kernelization: new upper and lower bound techniques. In: Proceedings of IWPEC 2009. Lect. Notes Comput. Sci., vol. 5917, pp. 17\u201337. Springer, Berlin (2009)"},{"issue":"8","key":"9428_CR6","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels (extended abstract). J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9428_CR7","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1007\/978-3-642-04128-0_57","volume-title":"Proceedings of ESA 2009","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. In: Proceedings of ESA 2009. Lect. Notes Comput. Sci., vol. 5757, pp. 635\u2013646. Springer, Berlin (2009)"},{"issue":"2","key":"9428_CR8","doi-asserted-by":"crossref","first-page":"335","DOI":"10.5802\/aif.357","volume":"20","author":"A. Bonami","year":"1970","unstructured":"Bonami, A.: \u00c9tude des coefficients de\u00a0Fourier des fonctions de L p (G). Ann. Inst. Fourier 20(2), 335\u2013402 (1970)","journal-title":"Ann. Inst. Fourier"},{"key":"9428_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84628-970-5","volume-title":"Graph Theory","author":"J.A. Bondy","year":"2008","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, New York (2008)"},{"key":"9428_CR10","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1007\/978-3-642-13731-0_17","volume-title":"Proceedings of SWAT 2010","author":"R. Crowston","year":"2010","unstructured":"Crowston, R., Gutin, G., Jones, M., Kim, E.J., Ruzsa, I.Z.: Systems of linear equations over $\\mathbb{F}_{2}$ and problems parameterized above average. In: Proceedings of SWAT 2010. Lect. Notes Comput. Sci., vol. 6139, pp. 164\u2013175. Springer, Berlin (2010)"},{"key":"9428_CR11","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-1-4612-2566-9_7","volume-title":"Proceedings of Feasible Mathematics II","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized computational feasibility. In: Clote, P., Remmel, J.B. (eds.): Proceedings of Feasible Mathematics II, pp. 219\u2013244. Birkh\u00e4user, Basel (1995)"},{"key":"9428_CR12","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":"9428_CR13","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"issue":"3","key":"9428_CR14","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theory Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theory Comput. Sci."},{"key":"9428_CR15","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News 38, 31\u201345 (2007)","journal-title":"ACM SIGACT News"},{"key":"9428_CR16","doi-asserted-by":"crossref","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, 521\u2013538 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"9428_CR17","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/s00453-007-9144-0","volume":"52","author":"G. Gutin","year":"2008","unstructured":"Gutin, G., Szeider, S., Yeo, A.: Fixed-parameter complexity of minimum profile problems. Algorithmica 52(2), 133\u2013152 (2008)","journal-title":"Algorithmica"},{"key":"9428_CR18","doi-asserted-by":"crossref","unstructured":"Gutin, G., Kim, E.J., Mnich, M., Yeo, A.: Betweenness parameterized above tight lower bound. J.\u00a0Comput. Syst. Sci. (2010). doi: 10.1016\/j.jcss.2010.05.001","DOI":"10.1016\/j.jcss.2010.05.001"},{"key":"9428_CR19","doi-asserted-by":"crossref","unstructured":"Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: A probabilistic approach to problems parameterized above tight lower bound. J. Comput. Syst. Sci. (2010). doi: 10.1016\/j.jcss.2010.06.001","DOI":"10.1016\/j.jcss.2010.06.001"},{"issue":"4","key":"9428_CR20","doi-asserted-by":"crossref","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 48(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"issue":"2","key":"9428_CR21","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1002\/rsa.20031","volume":"25","author":"J. H\u00e5stad","year":"2004","unstructured":"H\u00e5stad, J., Venkatesh, S.: On the advantage over a random assignment. Random Struct. Algorithms 25(2), 117\u2013149 (2004)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"9428_CR22","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1137\/0218026","volume":"18","author":"K. Iwama","year":"1989","unstructured":"Iwama, K.: CNF-satisfiability test by counting and polynomial average time. SIAM J. Comput. 18(2), 385\u2013391 (1989)","journal-title":"SIAM J. Comput."},{"key":"9428_CR23","doi-asserted-by":"crossref","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. In: Proceedings of the 5th Annual ACM Symposium on Theory of Computing, pp. 38\u201349 (1973)","DOI":"10.1145\/800125.804034"},{"issue":"2","key":"9428_CR24","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"},{"issue":"2","key":"9428_CR25","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.jcss.2008.08.004","volume":"75","author":"M. Mahajan","year":"2009","unstructured":"Mahajan, M., Raman, V., Sikdar, S.: Parameterizing above or below guaranteed values. J. Comput. Syst. Sci. 75(2), 137\u2013153 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9428_CR26","series-title":"Oxford Lecture Series in Mathematics and Its Applications","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 Lecture Series in Mathematics and Its Applications. Oxford University Press, London (2006)"},{"key":"9428_CR27","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R.: Some topics in analysis of boolean functions. In: Proceedings of STOC 2008, pp.\u00a0569\u2013578 (2008)","DOI":"10.1145\/1374376.1374458"},{"issue":"4","key":"9428_CR28","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/s10472-005-7036-z","volume":"44","author":"H. Shen","year":"2005","unstructured":"Shen, H., Zhang, H.: Improving exact algorithms for MAX-2-SAT. Ann. Math. Artif. Intell. 44(4), 419\u2013436 (2005)","journal-title":"Ann. Math. Artif. Intell."},{"issue":"5","key":"9428_CR29","doi-asserted-by":"crossref","first-page":"2007","DOI":"10.1137\/070710913","volume":"38","author":"Y. Villanger","year":"2009","unstructured":"Villanger, Y., Heggernes, P., Paul, C., Telle, J.A.: Interval completion with few edges. SIAM J. Comput. 38(5), 2007\u20132020 (2009)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9428-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9428-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9428-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:26:26Z","timestamp":1559276786000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9428-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,17]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["9428"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9428-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7,17]]}}}