{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:50Z","timestamp":1740109250481,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,4,19]],"date-time":"2017-04-19T00:00:00Z","timestamp":1492560000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["280152"],"award-info":[{"award-number":["280152"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft (DE)","doi-asserted-by":"publisher","award":["BL511\/10-1"],"award-info":[{"award-number":["BL511\/10-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,9]]},"DOI":"10.1007\/s00453-017-0310-8","type":"journal-article","created":{"date-parts":[[2017,4,19]],"date-time":"2017-04-19T09:20:17Z","timestamp":1492593617000},"page":"230-250","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Complexity and Approximability of Parameterized MAX-CSPs"],"prefix":"10.1007","volume":"79","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8955-0786","authenticated-orcid":false,"given":"Holger","family":"Dell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Lampis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valia","family":"Mitsou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,4,19]]},"reference":[{"issue":"4","key":"310_CR1","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1007\/s00037-011-0033-1","volume":"20","author":"M Alekhnovich","year":"2011","unstructured":"Alekhnovich, M., Razborov, A.A.: Satisfiability, branch-width and Tseitin tautologies. Comput. Complex. 20(4), 649\u2013678 (2011)","journal-title":"Comput. Complex."},{"issue":"1&2","key":"310_CR2","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(94)00254-G","volume":"147","author":"E Amaldi","year":"1995","unstructured":"Amaldi, E., Kann, V.: The complexity and approximability of finding maximum feasible subsystems of linear relations. Theor. Comput. Sci. 147(1&2), 181\u2013210 (1995)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"310_CR3","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/S0304-3975(97)00115-1","volume":"209","author":"E Amaldi","year":"1998","unstructured":"Amaldi, E., Kann, V.: On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems. Theor. Comput. Sci. 209(1\u20132), 237\u2013260 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"310_CR4","doi-asserted-by":"crossref","unstructured":"Austrin, P., Khot, S.: A characterization of approximation resistance for even k-partite csps. In: Kleinberg, R.D. (ed.) Innovations in Theoretical Computer Science, ITCS \u201913, Berkeley, pp. 187\u2013196. ACM (2013)","DOI":"10.1145\/2422436.2422459"},{"issue":"2","key":"310_CR5","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"310_CR6","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1006\/jcss.1995.1087","volume":"51","author":"N Creignou","year":"1995","unstructured":"Creignou, N.: A dichotomy theorem for maximum generalized satisfiability problems. J. Comput. Syst. Sci. 51(3), 511\u2013522 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"310_CR7","doi-asserted-by":"crossref","unstructured":"De, A., Mossel, E., Neeman, J.: Majority is stablest: discrete and sos. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, pp. 477\u2013486. ACM (2013)","DOI":"10.1145\/2488608.2488668"},{"key":"310_CR8","series-title":"Texts in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"key":"310_CR9","doi-asserted-by":"crossref","unstructured":"Elbassioni, K.M., Raman, R., Ray, S., Sitters, R.: On the approximability of the maximum feasible subsystem problem with 0\/1-coefficients. In Mathieu, C. (ed.) Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, pp. 1210\u20131219. SIAM (2009)","DOI":"10.1137\/1.9781611973068.131"},{"issue":"6","key":"310_CR10","doi-asserted-by":"crossref","first-page":"1558","DOI":"10.1137\/120865094","volume":"41","author":"V Feldman","year":"2012","unstructured":"Feldman, V., Guruswami, V., Raghavendra, P., Wu, Y.: Agnostic learning of monomials by halfspaces is hard. SIAM J. Comput. 41(6), 1558\u20131590 (2012)","journal-title":"SIAM J. Comput."},{"key":"310_CR11","doi-asserted-by":"crossref","unstructured":"Ganian, R.: Twin-cover: beyond vertex cover in parameterized algorithmics. In: Marx, D., Rossmanith, P. (eds.) Parameterized and Exact Computation\u20146th International Symposium, IPEC 2011, Saarbr\u00fccken. Revised Selected Papers, vol. 7112, pp. 259\u2013271 (2011)","DOI":"10.1007\/978-3-642-28050-4_21"},{"key":"310_CR12","unstructured":"Gaspers, S., Szeider, S.: Kernels for global constraints. In: Walsh, T. (ed.) IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, pp. 540\u2013545. IJCAI\/AAAI (2011)"},{"key":"310_CR13","doi-asserted-by":"crossref","unstructured":"Gaspers, S., Szeider, S.: Backdoors to acyclic SAT. In: Czumaj, A., Mehlhorn, K., Pitts, A.M., Wattenhofer, R. (eds.) Proceedings of Part I, Automata, Languages, and Programming\u201439th International Colloquium, ICALP 2012, Warwick. Lecture Notes in Computer Science, vol. 7391, pp. 363\u2013374. Springer (2012)","DOI":"10.1007\/978-3-642-31594-7_31"},{"key":"310_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2014.06.006","volume":"216","author":"S Gaspers","year":"2014","unstructured":"Gaspers, S., Szeider, S.: Guarantees and limits of preprocessing in constraint satisfaction and reasoning. Artif. Intell. 216, 1\u201319 (2014)","journal-title":"Artif. Intell."},{"key":"310_CR15","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The structure of tractable constraint satisfaction problems. In: Kralovic, R., Urzyczyn, P. (eds.) Proceedings of MFCS 2006, Star\u00e1 Lesn\u00e1, Slovakia. Lecture Notes in Computer Science, vol. 4162, pp. 58\u201372. Springer (2006)","DOI":"10.1007\/11821069_5"},{"key":"310_CR16","doi-asserted-by":"crossref","unstructured":"Gurski, F., Wanke, E.: The tree-width of clique-width bounded graphs without $$\\mathit{K}_{{n, n}}$$ K n , n . In: Brandes, U., Wagner, D. (eds.) Proceedings of Graph-Theoretic Concepts in Computer Science, 26th International Workshop, WG 2000, Konstanz. Lecture Notes in Computer Science, vol. 1928, pp. 196\u2013205. Springer (2000)","DOI":"10.1007\/3-540-40064-8_19"},{"issue":"2","key":"310_CR17","doi-asserted-by":"crossref","first-page":"742","DOI":"10.1137\/070685798","volume":"39","author":"V Guruswami","year":"2009","unstructured":"Guruswami, V., Raghavendra, P.: Hardness of learning halfspaces with noise. SIAM J. Comput. 39(2), 742\u2013765 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"310_CR18","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"},{"key":"310_CR19","doi-asserted-by":"crossref","unstructured":"Khanna, S., Sudan, M., Williamson, D.P.: A complete classification of the approximability of maximization problems derived from boolean constraint satisfaction. In: Leighton, F.T., Shor, P.W. (eds.) Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, pp. 11\u201320. ACM (1997)","DOI":"10.1145\/258533.258538"},{"key":"310_CR20","doi-asserted-by":"crossref","unstructured":"Khot, S., Saket, R.: Approximating csps using LP relaxation. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) Proceedings of Part I, Automata, Languages, and Programming\u201442nd International Colloquium, ICALP 2015, Kyoto. Lecture Notes in Computer Science, vol. 9134, pp. 822\u2013833. Springer (2015)","DOI":"10.1007\/978-3-662-47672-7_67"},{"issue":"1","key":"310_CR21","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s00453-011-9554-x","volume":"64","author":"M Lampis","year":"2012","unstructured":"Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64(1), 19\u201337 (2012)","journal-title":"Algorithmica"},{"issue":"4","key":"310_CR22","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"310_CR23","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. Comput. J. 51(1), 60\u201378 (2008)","journal-title":"Comput. J."},{"key":"310_CR24","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.tcs.2012.12.039","volume":"481","author":"S Ordyniak","year":"2013","unstructured":"Ordyniak, S., Paulusma, D., Szeider, S.: Satisfiability of acyclic and almost acyclic CNF formulas. Theor. Comput. Sci. 481, 85\u201399 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"310_CR25","unstructured":"Paulusma, D., Slivovsky, F., Szeider, S.: Model counting for CNF formulas of bounded modular treewidth. In: Portier, N., Wilke, T. (eds.) STACS 2013, February 27\u2013March 2, 2013, Kiel. LIPIcs, vol. 20, pp. 55\u201366. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2013)"},{"issue":"2","key":"310_CR26","first-page":"141","volume":"14","author":"R Pichler","year":"2014","unstructured":"Pichler, R., R\u00fcmmele, S., Szeider, S., Woltran, S.: Tractable answer-set programming with weight constraints: bounded treewidth is not enough. TPLP 14(2), 141\u2013164 (2014)","journal-title":"TPLP"},{"key":"310_CR27","doi-asserted-by":"crossref","unstructured":"S\u00e6ther, S.H., Telle, J.A., Vatshelle, M.: Solving maxsat and #sat on structured CNF formulas. In: Sinz, C., Egly, U. (eds.) Proceedings of SAT 2014\u2014Vienna. Lecture Notes in Computer Science, vol. 8561, pp. 16\u201331. Springer (2014)","DOI":"10.1007\/978-3-319-09284-3_3"},{"issue":"2","key":"310_CR28","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/j.jcss.2009.04.003","volume":"76","author":"M Samer","year":"2010","unstructured":"Samer, M., Szeider, S.: Constraint satisfaction with bounded treewidth revisited. J. Comput. Syst. Sci. 76(2), 103\u2013114 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"310_CR29","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Lipton, R.J., Burkhard, W.A., Savitch, W.J., Friedman, E.P., Aho, A.V. (eds.) Proceedings of the 10th Annual ACM Symposium on Theory of Computing, San Diego, pp. 216\u2013226. ACM (1978)","DOI":"10.1145\/800133.804350"},{"key":"310_CR30","doi-asserted-by":"crossref","unstructured":"Slivovsky, F., Szeider, S.: Model counting for formulas of bounded clique-width. In: Cai, L., Cheng, S., Lam, T.W. (eds.) Proceedings of ISAAC 2013, Hong Kong, China. Lecture Notes in Computer Science, vol. 8283, pp. 677\u2013687. Springer (2013)","DOI":"10.1007\/978-3-642-45030-3_63"},{"key":"310_CR31","unstructured":"Szeider, S.: On fixed-parameter tractable parameterizations of SAT. In: Giunchiglia, E., Tacchella, A. (eds.) Theory and Applications of Satisfiability Testing, 6th International Conference, SAT 2003. Santa Margherita Ligure, Selected Revised Papers. Lecture Notes in Computer Science, vol. 2919, pp. 188\u2013202. Springer (2003)"},{"key":"310_CR32","unstructured":"Szeider, S.: Not so easy problems for tree decomposable graphs. CoRR, abs\/1107.1177 (2011)"},{"key":"310_CR33","unstructured":"Szeider, S.: The parameterized complexity of constraint satisfaction and reasoning. In: Tompits, H., Abreu, S., Oetsch, J., P\u00fchrer, J., Seipel, D., Umeda, M., Wolf, A. (eds.) INAP 2011, and WLP 2011, Vienna, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7773, pp. 27\u201337. Springer (2011)"},{"issue":"1","key":"310_CR34","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/j.disopt.2010.07.003","volume":"8","author":"S Szeider","year":"2011","unstructured":"Szeider, S.: The parameterized complexity of k-flip local search for SAT and MAX SAT. Discrete Optim. 8(1), 139\u2013145 (2011)","journal-title":"Discrete Optim."},{"key":"310_CR35","doi-asserted-by":"publisher","unstructured":"Trevisan, L.: Inapproximability of combinatorial optimization problems. In: Paradigms of Combinatorial Optimization, 2nd edn, pp. 381\u2013434 (2014). doi: 10.1002\/9781119005353.ch13","DOI":"10.1002\/9781119005353.ch13"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0310-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0310-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0310-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,21]],"date-time":"2019-09-21T04:47:15Z","timestamp":1569041235000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0310-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,19]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["310"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0310-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,4,19]]}}}