{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,9]],"date-time":"2024-05-09T07:43:53Z","timestamp":1715240633272},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,2,21]],"date-time":"2008-02-21T00:00:00Z","timestamp":1203552000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,2,21]],"date-time":"2008-02-21T00:00:00Z","timestamp":1203552000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2008,12]]},"DOI":"10.1007\/s10601-007-9037-5","type":"journal-article","created":{"date-parts":[[2008,2,20]],"date-time":"2008-02-20T14:20:46Z","timestamp":1203517246000},"page":"437-458","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Minimization of Locally Defined Submodular Functions by Optimal Soft Arc Consistency"],"prefix":"10.1007","volume":"13","author":[{"given":"Martin C.","family":"Cooper","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,2,21]]},"reference":[{"key":"9037_CR1","unstructured":"Bessi\u00e8re, C., & R\u00e9gin, J.-C. (2001). Refining the basic constraint propagation algorithm. In Proc IJCAI\u201901 (pp.\u00a0309\u2013315). Seattle, WA."},{"key":"9037_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(85)90035-6","volume":"12","author":"A. Billionet","year":"1985","unstructured":"Billionet, A., & Minoux, M. (1985). Maximizing a supermodular pseudo-boolean function: A polynomial algorithm for cubic functions. Discrete Applied Mathematics, 12, 1\u201311.","journal-title":"Discrete Applied Mathematics"},{"key":"9037_CR3","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(01)00336-5","volume":"123","author":"E. Boros","year":"2002","unstructured":"Boros, E., & Hammer, P. L. (2002). Pseudo-boolean optimization. Discrete Applied Mathematics, 123, 155\u2013225.","journal-title":"Discrete Applied Mathematics"},{"key":"9037_CR4","doi-asserted-by":"crossref","unstructured":"Bulatov, A. A. (2002). A dichotomy theorem for constraints on a three-element set. In Proc. 43rd IEEE symposium on foundations of computer science (FOCS\u201902) (pp.\u00a0649\u2013658).","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"9037_CR5","doi-asserted-by":"crossref","unstructured":"Bulatov, A. A. (2003). Tractable conservative constraint satisfaction problems. In Proc. 18th IEEE symposium on logic in computer science (LICS\u201903) (pp.\u00a0321\u2013330).","DOI":"10.1109\/LICS.2003.1210072"},{"key":"9037_CR6","doi-asserted-by":"crossref","unstructured":"Bulatov, A. A. (2006). Combinatorial problems raised from 2-semilattices. Journal of Algebra, 321\u2013339.","DOI":"10.1016\/j.jalgebra.2004.07.044"},{"key":"9037_CR7","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A. A. Bulatov","year":"2005","unstructured":"Bulatov, A. A., Krokhin, A. A., & Jeavons, P. G. (2005). Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34, 720\u2013742.","journal-title":"SIAM Journal on Computing"},{"key":"9037_CR8","doi-asserted-by":"crossref","unstructured":"Cohen, D., Cooper, M. C., & Jeavons, P. (2004). A complete characterisation of complexity for Boolean constraint optimization problems., In Proc. 10th Int. Conf. on Priciples and Practice of Constraint Programming (CP\u201904), LNCS 3258 (pp.\u00a0212\u2013226).","DOI":"10.1007\/978-3-540-30201-8_18"},{"key":"9037_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1023\/B:AIRE.0000044479.89075.02","volume":"22","author":"D. Cohen","year":"2004","unstructured":"Cohen, D., Cooper, M. C., Jeavons, P., & Krokhin, A. (2004). A maximal tractable class of soft constraints. Journal of Artificial Intelligence Research, 22, 1\u201322.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9037_CR10","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. C., Jeavons, P., & Krokhin, A. (2005). Supermodular functions and the complexity of Max-CSP. Discrete Applied Mathematics, 149, 53\u201372.","journal-title":"Discrete Applied Mathematics"},{"issue":"11","key":"9037_CR11","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. C., Jeavons, P., & Krokhin, A. (2006). The complexity of soft constraint satisfaction. Artificial Intelligence, 170(11), 983\u20131016.","journal-title":"Artificial Intelligence"},{"key":"9037_CR12","doi-asserted-by":"crossref","unstructured":"Cohen, D., Cooper, M. C., & Jeavons, P. (2006). An algebraic characterisation of complexity for valued constraints. In Proc. CP\u201906, LNCS 4204 (pp.\u00a0107\u2013121).","DOI":"10.1007\/11889205_10"},{"key":"9037_CR13","doi-asserted-by":"crossref","unstructured":"Cohen, D., Cooper, M.C., & Jeavons, P. (2008). Generalising submodularity and horn clauses: Tractable optimization problems defined by tournament pair multimorphisms. Theoretical Computer Science (in press)","DOI":"10.1016\/j.tcs.2008.03.015"},{"key":"9037_CR14","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0165-0114(02)00134-3","volume":"134","author":"M. C. Cooper","year":"2003","unstructured":"Cooper, M. C. (2003). Reduction operations in fuzzy and valued constraint satisfaction. Fuzzy Sets and Systems, 134, 311\u2013342.","journal-title":"Fuzzy Sets and Systems"},{"key":"9037_CR15","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s10601-005-2240-3","volume":"10","author":"M. C. Cooper","year":"2005","unstructured":"Cooper, M. C. (2005). High-order consistency in valued constraint satisfaction. Constraints, 10, 283\u2013305.","journal-title":"Constraints"},{"key":"9037_CR16","unstructured":"Cooper, M. C., de Givry, S., & Schiex, T. (2007). Optimal soft arc consistency. In Proc. IJCAI\u201907 (pp.\u00a068\u201373). Hyderabad."},{"issue":"1\u20132","key":"9037_CR17","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.artint.2003.09.002","volume":"154","author":"M. C. Cooper","year":"2004","unstructured":"Cooper, M. C., & Schiex, T. (2004). Arc consistency for soft constraints. Artificial Intelligence, 154(1\u20132), 199\u2013227.","journal-title":"Artificial Intelligence"},{"issue":"3","key":"9037_CR18","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1006\/jcss.1995.1087","volume":"51","author":"N. Creignou","year":"1995","unstructured":"Creignou, N. (1995). A dichotomy theorem for maximum generalised satisfiability problems. Journal of Computer and Systems Sciences, 51(3), 511\u2013522.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"9037_CR19","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., & Sudan, M. (2001). Complexity classification of Boolean constraint satisfaction problems. In SIAM monographs on discrete mathematics and applications 7.","DOI":"10.1137\/1.9780898718546"},{"issue":"2","key":"9037_CR20","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/net.3230150206","volume":"15","author":"W. H. Cunningham","year":"1985","unstructured":"Cunningham, W. H. (1985). Minimum cuts, modular functions, and matroid polyhedra. Networks, 15(2), 205\u2013215.","journal-title":"Networks"},{"key":"9037_CR21","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/BF02579361","volume":"5","author":"W. H. Cunningham","year":"1985","unstructured":"Cunningham, W. H. (1985). On submodular function minimization. Combinatorica, 5, 185\u2013192.","journal-title":"Combinatorica"},{"key":"9037_CR22","unstructured":"Dechter, R. (2003). Constraint processing. Morgan Kaufmann."},{"issue":"1","key":"9037_CR23","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1998","unstructured":"Feder, T., & Vardi, M. Y. (1998). The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM Journal on Computing, 28(1), 57\u2013104.","journal-title":"SIAM Journal on Computing"},{"key":"9037_CR24","unstructured":"Fujishige, S. (2005). Submodular Functions and Optimisation. 2nd edn., Annals of discrete mathematics 58. Elsevier."},{"key":"9037_CR25","unstructured":"Fujishige, S., Hayashi, T., & Isotani, S. (2006). The minimum-norm-point algorithm applied to submodular function minimization and linear programming. Report RIMS1571, Research Institute for Mathematical Sciences, Kyoto University."},{"key":"9037_CR26","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0012-365X(00)00164-3","volume":"226","author":"S. Fujishige","year":"2001","unstructured":"Fujishige, S., & Patkar, S. B. (2001). Realization of set functions as cut functions of graphs and hypergraphs. Discrete Mathematics, 226, 199\u2013210.","journal-title":"Discrete Mathematics"},{"key":"9037_CR27","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. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35, 921\u2013940.","journal-title":"Journal of the ACM"},{"key":"9037_CR28","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., & Schrijver, A. (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 169\u2013198. (1984). Corrigendum: Combinatorica, 4, 291\u2013295.","DOI":"10.1007\/BF02579139"},{"issue":"2","key":"9037_CR29","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1006\/jctb.2001.2072","volume":"84","author":"S. Iwata","year":"2002","unstructured":"Iwata, S. (2002). A fully combinatorial algorithm for submodular function minimization. Journal of Combinatorial Theory, Series B, 84(2), 203\u2013212.","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"4","key":"9037_CR30","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/S0097539701397813","volume":"32","author":"S. Iwata","year":"2002","unstructured":"Iwata, S. (2002). A faster scaling algorithm for minimizing submodular functions. SIAM Journal on Computing, 32(4), 833\u2013840.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"9037_CR31","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. (2001). A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. Journal of the ACM, 48(4), 761\u2013777.","journal-title":"Journal of the ACM"},{"key":"9037_CR32","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P. G. Jeavons","year":"1998","unstructured":"Jeavons, P.G. (1998). On the algebraic structure of combinatorial problems. Theoretical Computer Science, 200, 185\u2013204.","journal-title":"Theoretical Computer Science"},{"key":"9037_CR33","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0004-3702(98)00022-8","volume":"101","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P., Cohen, D., & Cooper M. C. (1998). Constraints, consistency and closure. Artificial Intelligence, 101, 251\u2013265.","journal-title":"Artificial Intelligence"},{"key":"9037_CR34","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. G. Jeavons","year":"1997","unstructured":"Jeavons, P. G., Cohen D. A., & Gyssens, M. (1997). Closure properties of constraints. Journal of the ACM, 44, 527\u2013548.","journal-title":"Journal of the ACM"},{"issue":"2","key":"9037_CR35","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0004-3702(95)00107-7","volume":"79","author":"P. G. Jeavons","year":"1995","unstructured":"Jeavons, P. G., & Cooper, M. C. (1995). Tractable constraints on ordered domains. Artificial Intelligence, 79(2), 327\u2013339.","journal-title":"Artificial Intelligence"},{"issue":"6","key":"9037_CR36","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. (2006). The approximability of three-valued Max CSP. SIAM Journal on Computing, 35(6), 1329\u20131349.","journal-title":"SIAM Journal on Computing"},{"key":"9037_CR37","unstructured":"Koster, A. (1999). Frequency assignment\u2014models and algorithms. PhD thesis, The Netherlands: Universiteit Maastricht, ISBN 90-9013119-1."},{"issue":"3\u20135","key":"9037_CR38","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S0167-6377(98)00043-1","volume":"23","author":"A. M. C. A. Koster","year":"1998","unstructured":"Koster, A. M. C. A., van Hoesel, S. P. M., & Kolen, A. W. J. (1998). The partial constraint satisfaction problem: Facets and lifting theorems. Operations Research Letters, 23(3\u20135), 89\u201397.","journal-title":"Operations Research Letters"},{"key":"9037_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2004.05.004","volume":"159","author":"J. Larrosa","year":"2004","unstructured":"Larrosa, J., & Schiex, T. (2004). Solving weighted CSP by maintaining arc consistency. Artificial Intelligence, 159, 1\u201326.","journal-title":"Artificial Intelligence"},{"key":"9037_CR40","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/11889205_22","volume-title":"Proc. principles and practice of constraint programming - CP 2006, LNCS 4204","author":"C. Lecoutre","year":"2006","unstructured":"Lecoutre, C., & Szymanek, R. (2006). Generalized arc consistency for positive table constraints. In F. Benhamou (Ed.), Proc. principles and practice of constraint programming - CP 2006, LNCS 4204 (pp.\u00a0284\u2013298). Berlin: Springer-Verlag."},{"key":"9037_CR41","first-page":"321","volume-title":"Handbooks in operations research and management science 12","author":"S. T. McCormick","year":"2005","unstructured":"McCormick, S. T. (2005). Submodular function minimization in discrete optimization. In K. Aardal, G. L. Nemhauser, & R. Weismantel (Eds.), Handbooks in operations research and management science 12 (pp.\u00a0321\u2013391). Amsterdam: Elsevier."},{"key":"9037_CR42","doi-asserted-by":"crossref","unstructured":"Meseguer, P., Rossi, F., & Schiex, T. (2006). Soft constraints. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of constraint programming (pp.\u00a0281\u2013328). Elsevier.","DOI":"10.1016\/S1574-6526(06)80013-1"},{"key":"9037_CR43","unstructured":"Mohr, R., & Masini, G. (1988) Good old discrete relaxation. In Proc. European conf. artificial intelligence (pp.\u00a0651\u2013656). Munich."},{"key":"9037_CR44","volume-title":"Submodular functions and electrical networks","author":"H. Narayanan","year":"1997","unstructured":"Narayanan, H. (1997). Submodular functions and electrical networks. North-Holland, Amsterdam."},{"key":"9037_CR45","doi-asserted-by":"crossref","unstructured":"Orlin, J. B. (2007). A faster strongly polynomial time algorithm for submodular minimization. In M. Fischetti, & D. P. Williamson (Eds.), IPCO 2007, LNCS 4513 (pp.\u00a0240\u2013251).","DOI":"10.1007\/978-3-540-72792-7_19"},{"key":"9037_CR47","unstructured":"Schiex, T., Fargier, H., & Verfaillie, G. (1995). Valued constraint satisfaction problems: Hard and easy problems. In Proc. of the 14th IJCAI (pp.\u00a0631\u2013637). Montreal, Canada."},{"key":"9037_CR48","doi-asserted-by":"crossref","unstructured":"Schlesinger, D. (2007). Exact solution of permuted submodular MinSum problems. In Proc. of the 6th international conference on energy minimization methods in computer vision and pattern recognition, Ezhou, Hubei, China LNCS 4679 (Vol. 4679, pp. 28\u201338) Springer.","DOI":"10.1007\/978-3-540-74198-5_3"},{"key":"9037_CR49","first-page":"113","volume":"4","author":"M. Schlesinger","year":"1976","unstructured":"Schlesinger, M. (1976). Syntactic analysis of two-dimensional visual signals in noisy conditions. Kibernetika, 4, 113\u2013130 (In Russian).","journal-title":"Kibernetika"},{"key":"9037_CR50","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A. Schrijver","year":"2000","unstructured":"Schrijver, A. (2000). A combinatorial algorithm minimizing submodular functions in strongly polynomial time. Journal of Combinatorial Theory, Series B, 80, 346\u2013355.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"9037_CR51","unstructured":"Topkis, D. (1998). Supermodularity and complementarity. Princeton University Press."},{"issue":"7","key":"9037_CR52","doi-asserted-by":"publisher","first-page":"1165","DOI":"10.1109\/TPAMI.2007.1036","volume":"29","author":"T. Werner","year":"2007","unstructured":"Werner, T. (2007). A linear programming approach to max-sum problem: A review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(7), 1165\u20131179.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"9037_CR53","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/BF01580381","volume":"11","author":"P. Wolfe","year":"1976","unstructured":"Wolfe, P. (1976). Finding the nearest point in a polytope. Mathematical Programming, 11, 128\u2013149.","journal-title":"Mathematical Programming"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-007-9037-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10601-007-9037-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-007-9037-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-007-9037-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,16]],"date-time":"2022-05-16T00:33:57Z","timestamp":1652661237000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10601-007-9037-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2,21]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["9037"],"URL":"https:\/\/doi.org\/10.1007\/s10601-007-9037-5","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2,21]]},"assertion":[{"value":"13 June 2007","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2007","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 February 2008","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}