{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T04:01:20Z","timestamp":1773201680215,"version":"3.50.1"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"Renyi Institute"},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ERC-2018-SYG 810115"],"award-info":[{"award-number":["ERC-2018-SYG 810115"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["LP2021-1\/2021"],"award-info":[{"award-number":["LP2021-1\/2021"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"publisher","award":["&#x00DA"],"award-info":[{"award-number":["&#x00DA"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"publisher","award":["NKP-23-3"],"award-info":[{"award-number":["NKP-23-3"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"publisher","award":["EP\/X030989\/1"],"award-info":[{"award-number":["EP\/X030989\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2026,3,31]]},"DOI":"10.1137\/24m1675357","type":"journal-article","created":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T07:00:42Z","timestamp":1773126042000},"page":"308-335","source":"Crossref","is-referenced-by-count":0,"title":["Monotonic Decompositions of Submodular Set Functions"],"prefix":"10.1137","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0457-4573","authenticated-orcid":true,"given":"Krist\u00f3f","family":"B\u00e9rczi","sequence":"first","affiliation":[{"name":"MTA-ELTE Matroid Optimization Research Group and HUN-REN\u2013ELTE Egerv\u00e1ry Research Group, Department of Operations Research, E\u00f6tv\u00f6s Lor\u00e1nd University, and HUN-REN Alfr\u00e9d R\u00e9nyi Institute of Mathematics, Budapest, Hungary."}]},{"given":"Bogl\u00e1rka","family":"Geh\u00e9r","sequence":"additional","affiliation":[{"name":"Department of Applied Analysis and Computational Mathematics, E\u00f6tv\u00f6s Lor\u00e1nd University, and HUN-REN Alfr\u00e9d R\u00e9nyi Institute of Mathematics, Budapest, Hungary."}]},{"given":"Andr\u00e1s","family":"Imolay","sequence":"additional","affiliation":[{"name":"Department of Operations Research, E\u00f6tv\u00f6s Lor\u00e1nd University, Budapest, Hungary."}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6596-0465","authenticated-orcid":true,"given":"L\u00e1szl\u00f3","family":"Lov\u00e1sz","sequence":"additional","affiliation":[{"name":"HUN-REN Alfr\u00e9d R\u00e9nyi Institute of Mathematics, Budapest, Hungary."}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0373-7414","authenticated-orcid":true,"given":"Tam\u00e1s","family":"Schwarcz","sequence":"additional","affiliation":[{"name":"Department of Mathematics, London School of Economics and Political Science, London, England, United Kingdom."}]}],"member":"351","published-online":{"date-parts":[[2026,3,10]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00103-1"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1248-6"},{"key":"ref3","unstructured":"W. Bai and J. Bilmes, Greed is still good: Maximizing monotone submodular+supermodular (BP) functions, in Proceedings of the 35th International Conference on Machine Learning, Proc. Mach. Learn. Res. 80, J. Dy and A. Krause, eds. 2018, pp. 304\u2013313."},{"key":"ref4","series-title":"LIPIcs. Leibniz Int. Proc. Inform. 145","first-page":"30:1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2019)","author":"Bhaskar U.","year":"2019"},{"key":"ref5","unstructured":"J. Bilmes, Submodularity in Machine Learning and Artificial Intelligence, preprint, arXiv:2202.00132, 2022."},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"Y. Y. Boykov and M.P. Jolly, Interactive graph cuts for optimal boundary & region segmentation of objects in ND images, in Proceedings of the 8th IEEE International Conference on Computer Vision, IEEE, 2001, pp. 105\u2013112.","DOI":"10.1109\/ICCV.2001.937505"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"D. Chakrabarty and Z. Huang, Testing coverage functions, in Proceedings of the 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012, Part I, Springer, Heidelberg, 2012, pp. 170\u2013181.","DOI":"10.1007\/978-3-642-31594-7_15"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/140964072"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1137\/100803869"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.5802\/aif.53"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.8.789"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-2434-0"},{"key":"ref13","first-page":"69","volume-title":"Combinatorial Structures and Their Applications","author":"Edmonds J.","year":"1970"},{"key":"ref14","unstructured":"M. El Halabi, G. Orfanides, and T. Hoheisel, Difference of submodular minimization via DC programming, in Proceedings of the International Conference on Machine Learning, 2023, pp. 9172\u20139201."},{"key":"ref15","first-page":"283","volume":"18","author":"Erd\u0151s P.","year":"1967","journal-title":"Mat. Lapok"},{"key":"ref16","series-title":"Oxford Lecture Ser. Math. Appl. 38","volume-title":"Connections in Combinatorial Optimization","author":"Frank A.","year":"2011"},{"key":"ref17","series-title":"Ann. Discrete Math. 58","volume-title":"Submodular Functions and Optimization","author":"Fujishige S.","year":"2005","edition":"2"},{"key":"ref18","unstructured":"D. F. Gleich, Finite Calculus: A Tutorial for Solving Nasty Sums, Combinatorics, Final paper, Stanford University, 2005."},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00183-6"},{"key":"ref21","unstructured":"R. Iyer and J. Bilmes, Algorithms for approximate minimization of the difference between submodular functions, with applications, in Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, AUAI Press, Arlington, VA, 2012, pp. 407\u2013417."},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"S. Jegelka and J. Bilmes, Submodularity beyond submodular energies: Coupling edges in graph cuts, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, IEEE Computer Society, Washington, DC, 2011, pp. 1897\u20131904.","DOI":"10.1109\/CVPR.2011.5995589"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, R. E. Miller, J. W. Thatcher, and J. D. Bohlinger, eds. Springer, Boston, 1972, pp. 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"ref25","unstructured":"A. Krause and C. Guestrin, Near-optimal nonmyopic value of information in graphical models, in Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence, 2005, pp. 324\u2013331."},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)00228-W"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190060206"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-68874-4_10"},{"key":"ref30","unstructured":"L. Lov\u00e1sz, Submodular Setfunctions on Sigma-Algebras, Version 2, preprint, arXiv:2302.04704, 2023."},{"key":"ref31","unstructured":"M. Narashiman and J. Bilmes, Submodular-super-modular procedure with applications to discriminative structure learning, in Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence, 2005, pp. 404\u2013410."},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392606"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/os-13.1.83"},{"key":"ref36","volume-title":"Theory of Charges:\u00a0A Study of Finitely Additive Measures","author":"Rao K. B.","year":"1983"},{"key":"ref37","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver A.","year":"2003"},{"key":"ref38","first-page":"257","volume":"29","author":"\u0160ipo\u0161 J.","year":"1979","journal-title":"Math. Slovaca"},{"key":"ref39","first-page":"103","volume":"10","author":"Staton W.","year":"1980","journal-title":"Ars Combin."},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.01.019"},{"key":"ref41","unstructured":"Z. Tuza, Conjecture, in Finite and Infinite Sets, Proc. Colloq. Math. Soc. Janos Bolyai, Budapest, Hungary, 1981."},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.04.005"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T07:01:00Z","timestamp":1773126060000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1675357"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,10]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1137\/24M1675357"],"URL":"https:\/\/doi.org\/10.1137\/24m1675357","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,10]]}}}