{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:46:48Z","timestamp":1725536808362},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642038150"},{"type":"electronic","value":"9783642038167"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-03816-7_63","type":"book-chapter","created":{"date-parts":[[2009,8,19]],"date-time":"2009-08-19T14:43:03Z","timestamp":1250692983000},"page":"744-757","source":"Crossref","is-referenced-by-count":0,"title":["The Expressive Power of Binary Submodular Functions"],"prefix":"10.1007","author":[{"given":"Stanislav","family":"\u017divn\u00fd","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David A.","family":"Cohen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter G.","family":"Jeavons","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"63_CR1","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.: Maximizing a supermodular pseudo-Boolean function: a polynomial algorithm for cubic functions. Discrete Applied Math.\u00a012, 1\u201311 (1985)","journal-title":"Discrete Applied Math."},{"issue":"1-3","key":"63_CR2","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(01)00341-9","volume":"123","author":"E. Boros","year":"2002","unstructured":"Boros, E., Hammer, P.L.: Pseudo-Boolean optimization. Discrete Applied Mathematics\u00a0123(1-3), 155\u2013225 (2002)","journal-title":"Discrete Applied Mathematics"},{"key":"63_CR3","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0166-218X(95)00103-X","volume":"70","author":"R. Burkard","year":"1996","unstructured":"Burkard, R., Klinz, B., Rudolf, R.: Perspectives of Monge properties in optimization. Discrete Applied Mathematics\u00a070, 95\u2013161 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"63_CR4","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 constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol.\u00a04204, pp. 107\u2013121. Springer, Heidelberg (2006)"},{"key":"63_CR5","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., Jeavons, P., Krokhin, A.: A maximal tractable class of soft constraints. Journal of Artificial Intelligence Research\u00a022, 1\u201322 (2004)","journal-title":"Journal of Artificial Intelligence Research"},{"key":"63_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 Applied Mathematics\u00a0149, 53\u201372 (2005)","journal-title":"Discrete Applied Mathematics"},{"key":"63_CR7","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, 983\u20131016 (2006)","journal-title":"Artificial Intelligence"},{"issue":"4","key":"63_CR8","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s10601-007-9037-5","volume":"13","author":"M. Cooper","year":"2008","unstructured":"Cooper, M.: Minimization of Locally Defined Submodular Functions by Optimal Soft Arc Consistency. Constraints\u00a013(4), 437\u2013458 (2008)","journal-title":"Constraints"},{"key":"63_CR9","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/BF01587085","volume":"44","author":"Y. Crama","year":"1989","unstructured":"Crama, Y.: Recognition problems for special classes of polynomials in 0-1 variables. Mathematical Programming\u00a044, 139\u2013155 (1989)","journal-title":"Mathematical Programming"},{"key":"63_CR10","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718546","volume-title":"Complexity Classification of Boolean Constraint Satisfaction Problems","author":"N. Creignou","year":"2001","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classification of Boolean Constraint Satisfaction Problems. SIAM, Philadelphia (2001)"},{"doi-asserted-by":"crossref","unstructured":"Deineko, V., Jonsson, P., Klasson, M., Krokhin, A.: The approximability of Max CSP with fixed-value constraints. Journal of the ACM\u00a055(4) (2008)","key":"63_CR11","DOI":"10.1145\/1391289.1391290"},{"doi-asserted-by":"crossref","unstructured":"Feige, U., Mirrokni, V.S., Vondr\u00e1k, J.: Maximizing non-monotone submodular functions. In: Proceedings of FOCS 2007 (2007)","key":"63_CR12","DOI":"10.1109\/FOCS.2007.29"},{"key":"63_CR13","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"M. Fisher","year":"1978","unstructured":"Fisher, M., Nemhauser, G., Wolsey, L.: An analysis of approximations for maximizing submodular set functions-I. Mathematical Programming\u00a014, 265\u2013294 (1978)","journal-title":"Mathematical Programming"},{"key":"63_CR14","series-title":"Annals of Discrete Mathematics","volume-title":"Submodular Functions and Optimization","author":"S. Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Annals of Discrete Mathematics, vol.\u00a058. North-Holland, Amsterdam (2005)","edition":"2"},{"key":"63_CR15","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01589108","volume":"45","author":"G. Gallo","year":"1988","unstructured":"Gallo, G., Simeone, B.: On the supermodular knapsack problem. Mathematical Programming\u00a045, 295\u2013309 (1988)","journal-title":"Mathematical Programming"},{"key":"63_CR16","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1287\/opre.13.3.388","volume":"13","author":"P.L. Hammer","year":"1965","unstructured":"Hammer, P.L.: Some network flow problems solved with pseudo-Boolean programming. Operations Research\u00a013, 388\u2013399 (1965)","journal-title":"Operations Research"},{"key":"63_CR17","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s10107-006-0084-2","volume":"112","author":"S. Iwata","year":"2008","unstructured":"Iwata, S.: Submodular function minimization. Mathematical Programming\u00a0112, 45\u201364 (2008)","journal-title":"Mathematical Programming"},{"issue":"1-2","key":"63_CR18","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.: Constraints, consistency and closure. Artificial Intelligence\u00a0101(1-2), 251\u2013265 (1998)","journal-title":"Artificial Intelligence"},{"issue":"6","key":"63_CR19","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 Journal on Computing\u00a035(6), 1329\u20131349 (2006)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"63_CR20","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1109\/TPAMI.2004.1262177","volume":"26","author":"V. Kolmogorov","year":"2004","unstructured":"Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? IEEE Transactions on PAMI\u00a026(2), 147\u2013159 (2004)","journal-title":"IEEE Transactions on PAMI"},{"key":"63_CR21","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization","author":"B. Korte","year":"2007","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization, 4th edn. Algorithms and Combinatorics, vol.\u00a021. Springer, Heidelberg (2007)","edition":"4"},{"issue":"1","key":"63_CR22","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/060669565","volume":"22","author":"A. Krokhin","year":"2008","unstructured":"Krokhin, A., Larose, B.: Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction. SIAM Journal on Discrete Mathematics\u00a022(1), 312\u2013328 (2008)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"63_CR23","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198522195.001.0001","volume-title":"Graphical Models","author":"S.L. Lauritzen","year":"1996","unstructured":"Lauritzen, S.L.: Graphical Models. Oxford University Press, Oxford (1996)"},{"key":"63_CR24","first-page":"235","volume-title":"Math. Programming","author":"L. Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Bachem, A., Gr\u00f6tschel, M., Korte, B. (eds.) Math. Programming, pp. 235\u2013257. Springer, Berlin (1983)"},{"key":"63_CR25","series-title":"Contributions to the Theory of Games","first-page":"51","volume-title":"The double description method","author":"T. Motzkin","year":"1953","unstructured":"Motzkin, T., Raiffa, H., Thompson, G., Thrall, R.: The double description method. Contributions to the Theory of Games, vol.\u00a02, pp. 51\u201373. Princeton Univ. Press, Princeton (1953)"},{"doi-asserted-by":"crossref","unstructured":"Narayanan, H.: Submodular Functions and Electrical Networks (1997)","key":"63_CR26","DOI":"10.1016\/S0167-5060(08)70678-2"},{"doi-asserted-by":"crossref","unstructured":"Nemhauser, G., Wolsey, L.: Integer and Combinatorial Optimization (1988)","key":"63_CR27","DOI":"10.1002\/9781118627372"},{"key":"63_CR28","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s10107-007-0189-2","volume":"118","author":"J.B. Orlin","year":"2009","unstructured":"Orlin, J.B.: A faster strongly polynomial time algorithm for submodular function minimization. Mathematical Programming\u00a0118, 237\u2013251 (2009)","journal-title":"Mathematical Programming"},{"issue":"4","key":"63_CR29","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s11083-005-9026-5","volume":"22","author":"S. Promislow","year":"2005","unstructured":"Promislow, S., Young, V.: Supermodular functions on finite lattices. Order\u00a022(4), 389\u2013413 (2005)","journal-title":"Order"},{"issue":"3","key":"63_CR30","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1287\/mnsc.17.3.200","volume":"17","author":"J. Rhys","year":"1970","unstructured":"Rhys, J.: A selection problem of shared fixed costs and network flows. Management Science\u00a017(3), 200\u2013207 (1970)","journal-title":"Management Science"},{"unstructured":"Rossi, F., van Beek, P., Walsh, T.: The Handbook of Constraint Programming (2006)","key":"63_CR31"},{"key":"63_CR32","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol.\u00a024. Springer, Heidelberg (2003)"},{"unstructured":"Topkis, D.: Supermodularity and Complementarity (1998)","key":"63_CR33"},{"unstructured":"Zalesky, B.: Efficient determination of Gibbs estimators with submodular energy functions. arXiv:math\/0304041v1 (February 2008)","key":"63_CR34"},{"key":"63_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/978-3-540-85958-1_8","volume-title":"Principles and Practice of Constraint Programming","author":"S. \u017divn\u00fd","year":"2008","unstructured":"\u017divn\u00fd, S., Jeavons, P.G.: Classes of submodular constraints expressible by graph cuts. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol.\u00a05202, pp. 112\u2013127. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03816-7_63","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,15]],"date-time":"2024-03-15T23:18:40Z","timestamp":1710544720000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03816-7_63"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642038150","9783642038167"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03816-7_63","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}