{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T01:10:21Z","timestamp":1736039421848,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540292388"},{"type":"electronic","value":"9783540320500"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11564751_30","type":"book-chapter","created":{"date-parts":[[2005,10,18]],"date-time":"2005-10-18T13:31:28Z","timestamp":1129642288000},"page":"388-402","source":"Crossref","is-referenced-by-count":1,"title":["Maximum Constraint Satisfaction on Diamonds"],"prefix":"10.1007","author":[{"given":"Andrei","family":"Krokhin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benoit","family":"Larose","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/978-3-540-45220-1_6","volume-title":"Computer Science Logic","author":"F. B\u00f6rner","year":"2003","unstructured":"B\u00f6rner, F., Bulatov, A., Jeavons, P., Krokhin, A.: Quantified constraints: Algorithms and complexity. In: Baaz, M., Makowsky, J.A. (eds.) CSL 2003. LNCS, vol.\u00a02803, pp. 58\u201370. Springer, Heidelberg (2003)"},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: A dichotomy theorem for constraints on a 3-element set. In: FOCS 2002, pp. 649\u2013658 (2002)","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: Tractable conservative constraint satisfaction problems. In: LICS 2003, pp. 321\u2013330 (2003)","DOI":"10.1109\/LICS.2003.1210072"},{"key":"30_CR4","doi-asserted-by":"crossref","unstructured":"Bulatov, A., Dalmau, V.: Towards a dichotomy theorem for the counting constraint satisfaction problem. In: FOCS 2003, pp. 562\u2013571 (2003)","DOI":"10.1109\/SFCS.2003.1238229"},{"key":"30_CR5","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0166-218X(95)00103-X","volume":"70","author":"R.E. Burkard","year":"1996","unstructured":"Burkard, R.E., Klinz, B., Rudolf, R.: Perspectives of Monge properties in optimization. Discrete Applied Mathematics\u00a070, 95\u2013161 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"30_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/978-3-540-30201-8_18","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2004","author":"D. Cohen","year":"2004","unstructured":"Cohen, D., Cooper, M., Jeavons, P.: A complete characterization of complexity for Boolean constraint optimization problems. In: Wallace, M. (ed.) CP 2004. LNCS, vol.\u00a03258, pp. 212\u2013226. Springer, Heidelberg (2004)"},{"key":"30_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-540-45193-8_17","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"D. Cohen","year":"2003","unstructured":"Cohen, D., Cooper, M., Jeavons, P., Krokhin, A.: Soft constraints: complexity and multimorphisms. In: Rossi, F. (ed.) CP 2003. LNCS, vol.\u00a02833, pp. 244\u2013258. Springer, Heidelberg (2003)"},{"key":"30_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/978-3-540-24749-4_14","volume-title":"STACS 2004","author":"D. Cohen","year":"2004","unstructured":"Cohen, D., Cooper, M., Jeavons, P., Krokhin, A.: Identifying efficiently solvable cases of Max CSP. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol.\u00a02996, pp. 152\u2013163. Springer, Heidelberg (2004)"},{"key":"30_CR9","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences\u00a051, 511\u2013522 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"30_CR10","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718546","volume-title":"Complexity Classifications of Boolean Constraint Satisfaction Problems","author":"N. Creignou","year":"2001","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM, Philadelphia (2001)"},{"issue":"6","key":"30_CR11","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/S0020-0190(02)00435-0","volume":"85","author":"M. Datar","year":"2003","unstructured":"Datar, M., Feder, T., Gionis, A., Motwani, R., Panigrahy, R.: A combinatorial algorithm for MAX CSP. Information Processing Letters\u00a085(6), 307\u2013315 (2003)","journal-title":"Information Processing Letters"},{"key":"30_CR12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511809088","volume-title":"Introduction to Lattices and Order","author":"B.A. Davey","year":"2002","unstructured":"Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order, 2nd edn. Cambridge University Press, Cambridge (2002)","edition":"2"},{"issue":"1","key":"30_CR13","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1147\/rd.471.0025","volume":"47","author":"B.L. Dietrich","year":"2003","unstructured":"Dietrich, B.L., Hoffman, A.J.: On greedy algorithms, partially ordered sets, and submodular functions. IBM J. of Research and Development\u00a047(1), 25\u201330 (2003)","journal-title":"IBM J. of Research and Development"},{"issue":"2","key":"30_CR14","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1002\/rsa.20026","volume":"25","author":"L. Engebretsen","year":"2004","unstructured":"Engebretsen, L., Guruswami, V.: Is constraint satisfaction over two variables always easy? Random Structures and Algorithms\u00a025(2), 150\u2013178 (2004)","journal-title":"Random Structures and Algorithms"},{"key":"30_CR15","volume-title":"Submodular Functions and Optimization","author":"S. Fujishige","year":"1991","unstructured":"Fujishige, S.: Submodular Functions and Optimization. North-Holland, Amsterdam (1991)"},{"key":"30_CR16","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A. Goldberg","year":"1988","unstructured":"Goldberg, A., Tarjan, R.E.: A new approach to the maximum flow problem. J. ACM\u00a035, 921\u2013940 (1988)","journal-title":"J. ACM"},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. In: FOCS 2003, pp. 552\u2013561 (2003)","DOI":"10.1109\/SFCS.2003.1238228"},{"key":"30_CR18","doi-asserted-by":"publisher","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\u00a048, 798\u2013859 (2001)","journal-title":"J. ACM"},{"issue":"4","key":"30_CR19","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S. Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM\u00a048(4), 761\u2013777 (2001)","journal-title":"J. ACM"},{"issue":"1-2","key":"30_CR20","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0304-3975(98)00343-0","volume":"244","author":"P. Jonsson","year":"2000","unstructured":"Jonsson, P.: Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights. Theoret. Comput. Sci.\u00a0244(1-2), 189\u2013203 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"30_CR21","unstructured":"Jonsson, P., Klasson, M., Krokhin, A.: The approximability of three-valued Max CSP. Technical Report cs.CC\/0412042, CoRR (2004)"},{"key":"30_CR22","volume-title":"Supermodularity and Complementarity","author":"D. Topkis","year":"1998","unstructured":"Topkis, D.: Supermodularity and Complementarity. Princeton Univ. Press, Princeton (1998)"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming - CP 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11564751_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T00:44:17Z","timestamp":1736037857000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11564751_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540292388","9783540320500"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11564751_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}