{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T07:47:38Z","timestamp":1725522458042},"publisher-location":"Berlin, Heidelberg","reference-count":44,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540927990"},{"type":"electronic","value":"9783540928003"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-92800-3_10","type":"book-chapter","created":{"date-parts":[[2008,12,22]],"date-time":"2008-12-22T08:39:25Z","timestamp":1229935165000},"page":"255-282","source":"Crossref","is-referenced-by-count":7,"title":["Introduction to the Maximum Solution Problem"],"prefix":"10.1007","author":[{"given":"Peter","family":"Jonsson","sequence":"first","affiliation":[]},{"given":"Gustav","family":"Nordh","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"10_CR1","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1137\/S0895480191217569","volume":"7","author":"A. Ageev","year":"1994","unstructured":"Ageev, A.: On finding critical independent and vertex sets. SIAM J. Discrete Math.\u00a07(2), 293\u2013295 (1994)","journal-title":"SIAM J. Discrete Math."},{"key":"10_CR2","doi-asserted-by":"publisher","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":"10_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B. Baker","year":"1994","unstructured":"Baker, B.: Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM\u00a041, 153\u2013180 (1994)","journal-title":"Journal of the ACM"},{"issue":"3","key":"10_CR4","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1093\/logcom\/exi083","volume":"16","author":"M. Bodirsky","year":"2006","unstructured":"Bodirsky, M., Ne\u0161et\u0159il, J.: Constraint satisfaction with countable homogeneous templates. Journal of Logic and Computation\u00a016(3), 359\u2013373 (2006)","journal-title":"Journal of Logic and Computation"},{"key":"10_CR5","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":"10_CR6","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":"10_CR7","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":"10_CR8","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":"10_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/11889205_10","volume-title":"Principles and Practice of Constraint Programming - CP 2006","author":"D. Cohen","year":"2006","unstructured":"Cohen, D., Cooper, M., Jeavons, P.: An algebraic characterisation of complexity for valued constraint. In: Benhamou, F. (ed.) CP 2006. LNCS, vol.\u00a04204, pp. 107\u2013121. Springer, Heidelberg (2006)"},{"issue":"11","key":"10_CR10","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1016\/j.artint.2006.04.002","volume":"170","author":"D. Cohen","year":"2006","unstructured":"Cohen, D., Cooper, M., Jeavons, P., Krokhin, A.: The complexity of soft constraint satisfaction. Artificial Intelligence\u00a0170(11), 983\u20131016 (2006)","journal-title":"Artificial Intelligence"},{"issue":"2","key":"10_CR11","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s00224-007-9003-z","volume":"42","author":"N. Creignou","year":"2008","unstructured":"Creignou, N., Hermann, M., Krokhin, A., Salzer, G.: Complexity of clausal constraints over chains. Theory Comput. Syst.\u00a042(2), 239\u2013255 (2008)","journal-title":"Theory Comput. Syst."},{"key":"10_CR12","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","key":"10_CR13","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1006\/inco.2000.3011","volume":"167","author":"P. Crescenzi","year":"2001","unstructured":"Crescenzi, P., Silvestri, R., Trevisan, L.: On weighted vs unweighted versions of combinatorial optimization problems. Inf. Comput.\u00a0167(1), 10\u201326 (2001)","journal-title":"Inf. Comput."},{"issue":"1-2","key":"10_CR14","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-2), 61\u201385 (2005)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s004939970003","volume":"19","author":"T. Feder","year":"1999","unstructured":"Feder, T., Hell, P., Huang, J.: List homomorphisms and circular arc graphs. Combinatorica\u00a019, 487\u2013505 (1999)","journal-title":"Combinatorica"},{"issue":"1","key":"10_CR16","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":"10_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-540-25984-8_17","volume-title":"Automated Reasoning","author":"\u00c0. Gil","year":"2004","unstructured":"Gil, \u00c0., Hermann, M., Salzer, G., Zanuttini, B.: Efficient algorithms for constraint description problems over finite totally ordered domains. In: Basin, D., Rusinowitch, M. (eds.) IJCAR 2004. LNCS, vol.\u00a03097, pp. 244\u2013258. Springer, Heidelberg (2004)"},{"key":"10_CR18","doi-asserted-by":"crossref","unstructured":"Goldmann, M., Russell, A.: The complexity of solving equations over finite groups. In: IEEE Conference on Computational Complexity, pp. 80\u201386 (1999)","DOI":"10.1109\/CCC.1999.766266"},{"issue":"4","key":"10_CR19","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1016\/j.ejc.2007.11.012","volume":"29","author":"G. Gutin","year":"2008","unstructured":"Gutin, G., Hell, P., Rafiey, A., Yeo, A.: A dichotomy for minimum cost graph homomorphisms. European J. Combin.\u00a029(4), 900\u2013911 (2008)","journal-title":"European J. Combin."},{"issue":"6","key":"10_CR20","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1016\/j.dam.2005.11.006","volume":"154","author":"G. Gutin","year":"2006","unstructured":"Gutin, G., Rafiey, A., Yeo, A.: Minimum cost and list homomorphisms to semicomplete digraphs. Discrete Applied Mathematics\u00a0154(6), 890\u2013897 (2006)","journal-title":"Discrete Applied Mathematics"},{"issue":"6","key":"10_CR21","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1016\/j.dam.2005.06.012","volume":"154","author":"G. Gutin","year":"2006","unstructured":"Gutin, G., Rafiey, A., Yeo, A., Tso, M.: Level of repair analysis and minimum cost homomorphisms of graphs. Discrete Applied Mathematics\u00a0154(6), 881\u2013889 (2006)","journal-title":"Discrete Applied Mathematics"},{"key":"10_CR22","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-colouring. Journal of Combinatorial Theory B\u00a048, 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory B"},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"H\u00e4hnle, R.: Complexity of many-valued logics. In: Proceedings of the 31st IEEE International Symposium on Multiple-valued Logic (ISMVL 2001), pp. 137\u2013148 (2001)","DOI":"10.1109\/ISMVL.2001.924565"},{"key":"10_CR24","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/BF01585160","volume":"62","author":"D. Hochbaum","year":"1993","unstructured":"Hochbaum, D., Megiddo, N., Naor, J., Tamir, A.: Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Mathematical Programming\u00a062, 69\u201384 (1993)","journal-title":"Mathematical Programming"},{"issue":"6","key":"10_CR25","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1137\/S0097539793251876","volume":"23","author":"D. Hochbaum","year":"1994","unstructured":"Hochbaum, D., 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."},{"issue":"4","key":"10_CR26","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. Journal of the ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"Journal of the ACM"},{"issue":"4","key":"10_CR27","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. Journal of the ACM\u00a048(4), 761\u2013777 (2001)","journal-title":"Journal of the ACM"},{"key":"10_CR28","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":"10_CR29","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":"1-2","key":"10_CR30","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. Theoretical Computer Science\u00a0244(1-2), 189\u2013203 (2000)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"10_CR31","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(3), 1329\u20131349 (2006)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10_CR32","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/060669231","volume":"38","author":"P. Jonsson","year":"2008","unstructured":"Jonsson, P., Kuivinen, F., Nordh, G.: Max Ones generalised to larger domains. SIAM J. Comput.\u00a038(1), 329\u2013365 (2008)","journal-title":"SIAM J. Comput."},{"key":"10_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/11821069_48","volume-title":"Mathematical Foundations of Computer Science 2006","author":"P. Jonsson","year":"2006","unstructured":"Jonsson, P., Nordh, G.: Generalised integer programming based on logically defined relations. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 549\u2013560. Springer, Heidelberg (2006)"},{"key":"10_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-540-74456-6_22","volume-title":"Mathematical Foundations of Computer Science 2007","author":"P. Jonsson","year":"2007","unstructured":"Jonsson, P., Nordh, G., Thapper, J.: The maximum solution problem on graphs. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 228\u2013239. Springer, Heidelberg (2007)"},{"issue":"6","key":"10_CR35","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.: The approximability of constraint satisfaction problems. SIAM J. Comput.\u00a030(6), 1863\u20131920 (2001)","journal-title":"SIAM J. Comput."},{"key":"10_CR36","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\n                \n                  p\n                . In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 628\u2013639. Springer, Heidelberg (2005)"},{"key":"10_CR37","doi-asserted-by":"crossref","unstructured":"P\u00f6schel, R., Kaluznin, L.: Funktionen- und Relationenalgebren. DVW, Berlin (1979)","DOI":"10.1007\/978-3-0348-5547-1"},{"key":"10_CR38","volume-title":"Lectures in Universal Algebra","author":"I. Rosenberg","year":"1986","unstructured":"Rosenberg, I.: Minimal clones I: the five types. In: Szab\u00f3, L., Szendrei, \u00c1. (eds.) Lectures in Universal Algebra. North-Holland, Amsterdam (1986)"},{"key":"10_CR39","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A. Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm for minimizing submodular functions in polynomial time. Journal of Combinatorial Theory B\u00a080, 346\u2013355 (2000)","journal-title":"Journal of Combinatorial Theory B"},{"key":"10_CR40","unstructured":"Szczepara, B.: Minimal clones generated by groupoids. PhD thesis, Universit\u00e9 de Montr\u00e9al (1996)"},{"key":"10_CR41","unstructured":"Szendrei, \u00c1.: Clones in Universal Algebra. In: S\u00e9minaires de Math\u00e9matiques Sup\u00e9rieures, University of Montreal, vol.\u00a099 (1986)"},{"issue":"1","key":"10_CR42","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/S0167-6377(01)00114-6","volume":"30","author":"G. Woeginger","year":"2002","unstructured":"Woeginger, G.: An efficient algorithm for a class of constraint satisfaction problems. Operations Research Letters\u00a030(1), 9\u201316 (2002)","journal-title":"Operations Research Letters"},{"issue":"3","key":"10_CR43","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0403037","volume":"3","author":"C. Zhang","year":"1990","unstructured":"Zhang, C.: Finding critical independent sets and critical vertex subsets are polynomial problems. SIAM J. Discrete Math.\u00a03(3), 431\u2013438 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"10_CR44","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the 38th ACM Symposium on Theory of Computing (STOC 2006), pp. 681\u2013690 (2006)","DOI":"10.1145\/1132516.1132612"}],"container-title":["Lecture Notes in Computer Science","Complexity of Constraints"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92800-3_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,4]],"date-time":"2019-03-04T16:18:29Z","timestamp":1551716309000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92800-3_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540927990","9783540928003"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92800-3_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}