{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T14:40:36Z","timestamp":1737384036312,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540745099"},{"type":"electronic","value":"9783540745105"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74510-5_20","type":"book-chapter","created":{"date-parts":[[2007,8,21]],"date-time":"2007-08-21T15:11:35Z","timestamp":1187709095000},"page":"182-193","source":"Crossref","is-referenced-by-count":1,"title":["Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems"],"prefix":"10.1007","author":[{"given":"Peter","family":"Jonsson","sequence":"first","affiliation":[]},{"given":"Andrei","family":"Krokhin","sequence":"additional","affiliation":[]},{"given":"Fredrik","family":"Kuivinen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and approximation: Combinatorial Optimization Problems and their Approximability Properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and approximation: Combinatorial Optimization Problems and their Approximability Properties. Springer, Heidelberg (1999)"},{"key":"20_CR2","first-page":"321","volume-title":"LICS 2003","author":"A. Bulatov","year":"2003","unstructured":"Bulatov, A.: Tractable conservative constraint satisfaction problems. In: LICS 2003. Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, pp. 321\u2013330. IEEE Computer Society Press, Los Alamitos (2003)"},{"issue":"1","key":"20_CR3","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"A. Bulatov","year":"2006","unstructured":"Bulatov, A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM\u00a053(1), 66\u2013120 (2006)","journal-title":"J. ACM"},{"issue":"3","key":"20_CR4","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A., Jeavons, P., Krokhin, A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput.\u00a034(3), 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"key":"20_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-8130-3","volume-title":"A Course in Universal Algebra","author":"S. Burris","year":"1981","unstructured":"Burris, S., Sankappanavar, H.: A Course in Universal Algebra. Springer, Heidelberg (1981)"},{"issue":"1-3","key":"20_CR6","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.dam.2005.03.003","volume":"149","author":"D. Cohen","year":"2005","unstructured":"Cohen, D., Cooper, M., Jeavons, P., Krokhin, A.: Supermodular functions and the complexity of Max CSP. Discrete Appl. Math.\u00a0149(1-3), 53\u201372 (2005)","journal-title":"Discrete Appl. Math."},{"key":"20_CR7","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/S0304-3975(03)00342-6","volume":"306","author":"V. Dalmau","year":"2003","unstructured":"Dalmau, V., Jeavons, P.: Learnability of quantified formulas. Theor. Comput. Sci.\u00a0306, 485\u2013511 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"Deineko, V., Jonsson, P., Klasson, M., Krokhin, A.: Supermodularity on chains and complexity of maximum constraint satisfaction. In: EuroComb 2005. European Conference on Combinatorics, Graph Theory and Applications, volume\u00a0AE of DMTCS Proceedings, pp. 51\u201356, 2005. Discrete Mathematics and Theoretical Computer Science, Full version available as The approximability of Max CSP with fixed-value constraints, arXiv.org:cs.CC\/0602075 (2005)","DOI":"10.46298\/dmtcs.3420"},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1016\/j.disc.2005.09.030","volume":"307","author":"T. Feder","year":"2007","unstructured":"Feder, T., Hell, P., Huang, J.: List homomorphisms of graphs with bounded degrees. Discrete Math.\u00a0307, 386\u2013392 (2007)","journal-title":"Discrete Math."},{"key":"20_CR10","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"P. Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004)"},{"issue":"6","key":"20_CR11","doi-asserted-by":"publisher","first-page":"1329","DOI":"10.1137\/S009753970444644X","volume":"35","author":"P. Jonsson","year":"2006","unstructured":"Jonsson, P., Klasson, M., Krokhin, A.: The approximability of three-valued Max CSP. SIAM J. Comput.\u00a035(6), 1329\u20131349 (2006)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"20_CR12","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1016\/j.jcss.2007.02.001","volume":"73","author":"P. Jonsson","year":"2007","unstructured":"Jonsson, P., Krokhin, A.: Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. J. Comput. System Sci.\u00a073(5), 691\u2013702 (2007)","journal-title":"J. Comput. System Sci."},{"issue":"6","key":"20_CR13","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S. Khanna","year":"2000","unstructured":"Khanna, S., Sudan, M., Trevisan, L., Williamson, D.P.: The approximability of constraint satisfaction problems. SIAM J. Comput.\u00a030(6), 1863\u20131920 (2000)","journal-title":"SIAM J. Comput."},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Krokhin, A., Larose, B.: Maximum constraint satisfaction on diamonds. Technical Report CS-RR-408, University of Warwick, UK (2004)","DOI":"10.1007\/11564751_30"},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/11564751_30","volume-title":"Principles and Practice of Constraint Programming - CP 2005","author":"A. Krokhin","year":"2005","unstructured":"Krokhin, A., Larose, B.: Maximum constraint satisfaction on diamonds. In: van Beek, P. (ed.) CP 2005. LNCS, vol.\u00a03709, pp. 388\u2013402. Springer, Heidelberg (2005)"},{"issue":"3","key":"20_CR16","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1137\/0404035","volume":"4","author":"G. MacGillivray","year":"1991","unstructured":"MacGillivray, G.: On the complexity of colouring by vertex-transitive and arc-transistive digraphs. SIAM J. Discret. Math.\u00a04(3), 397\u2013408 (1991)","journal-title":"SIAM J. Discret. Math."},{"key":"20_CR17","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E. Petrank","year":"1994","unstructured":"Petrank, E.: The hardness of approximation: Gap location. Computational Complexity\u00a04, 133\u2013157 (1994)","journal-title":"Computational Complexity"},{"key":"20_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-5547-1","volume-title":"Funktionen- und Relationenalgebren","author":"R. P\u00f6schel","year":"1979","unstructured":"P\u00f6schel, R., Kalu\u017enin, L.: Funktionen- und Relationenalgebren. DVW, Berlin (1979)"},{"volume-title":"Handbook of Constraint Programming","year":"2006","key":"20_CR19","unstructured":"Rossi, F., van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming. Elsevier, Amsterdam (2006)"},{"key":"20_CR20","unstructured":"Trevisan, L.: Inapproximability of combinatorial optimization problems, arXiv.org:cs.CC\/0409043 (2004)"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74510-5_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T14:07:12Z","timestamp":1737382032000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74510-5_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540745099","9783540745105"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74510-5_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}