{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T02:10:21Z","timestamp":1736561421100,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540462675"},{"type":"electronic","value":"9783540462682"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11889205_20","type":"book-chapter","created":{"date-parts":[[2006,9,28]],"date-time":"2006-09-28T12:07:42Z","timestamp":1159445262000},"page":"256-270","source":"Crossref","is-referenced-by-count":1,"title":["Approximability of Integer Programming with Generalised Constraints"],"prefix":"10.1007","author":[{"given":"Peter","family":"Jonsson","sequence":"first","affiliation":[]},{"given":"Fredrik","family":"Kuivinen","sequence":"additional","affiliation":[]},{"given":"Gustav","family":"Nordh","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","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: A dichotomy theorem for constraints on a three-element set. In: Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS 2002), pp. 649\u2013658 (2002)","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: A graph of a relational structure and constraint satisfaction problems. In: Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), pp. 448\u2013457 (2004)","DOI":"10.1109\/LICS.2004.1319639"},{"issue":"1","key":"20_CR4","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. Journal of the ACM\u00a053(1), 66\u2013120 (2006)","journal-title":"Journal of the ACM"},{"issue":"3","key":"20_CR5","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_CR6","doi-asserted-by":"crossref","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.: The complexity of maximal constraint languages. In: Proceedings of the 33rd ACM Symposium on Theory of Computing (STOC 2001), pp. 667\u2013674 (2001)","DOI":"10.1145\/380752.380868"},{"key":"20_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.A. Cohen","year":"2003","unstructured":"Cohen, D.A., Cooper, M., Jeavons, P.G., Krokhin, A.A.: Soft constraints: Complexity and multimorphisms. In: Rossi, F. (ed.) CP 2003. LNCS, vol.\u00a02833, pp. 244\u2013258. Springer, Heidelberg (2003)"},{"issue":"3","key":"20_CR8","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1023\/B:CONS.0000036045.82829.94","volume":"9","author":"D.A. Cohen","year":"2004","unstructured":"Cohen, D.A.: Tractable decision for a constraint language implies tractable search. Constraints\u00a09(3), 219\u2013229 (2004)","journal-title":"Constraints"},{"key":"20_CR9","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":"1\u20132","key":"20_CR10","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s10472-005-1810-9","volume":"44","author":"V. Dalmau","year":"2005","unstructured":"Dalmau, V.: A new tractable class of constraint satisfaction problems. Annals of Mathematics and Artificial Intelligence\u00a044(1\u20132), 61\u201385 (2005)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"1","key":"20_CR11","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput.\u00a028(1), 57\u2013104 (1999)","journal-title":"SIAM J. Comput."},{"key":"20_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"issue":"6","key":"20_CR13","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1137\/S0097539793251876","volume":"23","author":"D.S. Hochbaum","year":"1994","unstructured":"Hochbaum, D.S., Naor, J.: Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM J. Comput.\u00a023(6), 1179\u20131192 (1994)","journal-title":"SIAM J. Comput."},{"key":"20_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-11493-9","volume-title":"Group-Theoretic Algorithms and Graph Isomorphism","author":"C.M. Hoffmann","year":"1982","unstructured":"Hoffmann, C.M.: Group-Theoretic Algorithms and Graph Isomorphism. LNCS, vol.\u00a0136. Springer, Heidelberg (1982)"},{"key":"20_CR15","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. Journal of the ACM\u00a044, 527\u2013548 (1997)","journal-title":"Journal of the ACM"},{"key":"20_CR16","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0004-3702(95)00107-7","volume":"79","author":"P. Jeavons","year":"1996","unstructured":"Jeavons, P., Cooper, M.: Tractable constraints on ordered domains. Artificial Intelligence\u00a079, 327\u2013339 (1996)","journal-title":"Artificial Intelligence"},{"issue":"5","key":"20_CR17","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/S0020-0190(98)00170-7","volume":"68","author":"P. Jonsson","year":"1998","unstructured":"Jonsson, P.: Near-optimal nonapproximability results for some NPO PB-complete problems. Information Processing Letters\u00a068(5), 249\u2013253 (1998)","journal-title":"Information Processing Letters"},{"issue":"6","key":"20_CR18","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."},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Jonsson, P., Kuivinen, F., Nordh, G.: Approximability of integer programming with generalised constraints. CoRR, cs.CC\/0602047 (2006)","DOI":"10.1007\/11889205_20"},{"issue":"6","key":"20_CR20","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S. Khanna","year":"2001","unstructured":"Khanna, S., Sudan, M., Trevisan, L., Williamson, D.P.: The approximability of constraint satisfaction problems. SIAM J. Comput.\u00a030(6), 1863\u20131920 (2001)","journal-title":"SIAM J. Comput."},{"key":"20_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1007\/11549345_54","volume-title":"Mathematical Foundations of Computer Science 2005","author":"F. Kuivinen","year":"2005","unstructured":"Kuivinen, F.: Tight approximability results for the maximum solution equation problem over z p . In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 628\u2013639. Springer, Heidelberg (2005)"},{"key":"20_CR22","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., Kaluznin, L.: Funktionen- und Relationenalgebren. DVW, Berlin (1979)"},{"key":"20_CR23","volume-title":"Theory of linear and integer programming","author":"A. Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of linear and integer programming. John Wiley & Sons, Inc., New York (1986)"},{"key":"20_CR24","unstructured":"Szczepara, B.: Minimal clones generated by groupoids. Ph.D thesis, Universit\u00e9 de M\u00f3ntreal (1996)"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming - CP 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11889205_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T01:32:26Z","timestamp":1736559146000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11889205_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540462675","9783540462682"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11889205_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}