{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T17:01:21Z","timestamp":1762102881054,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,7,28]],"date-time":"2024-07-28T00:00:00Z","timestamp":1722124800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,7,28]],"date-time":"2024-07-28T00:00:00Z","timestamp":1722124800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12071459","11991022","11771386","11728104"],"award-info":[{"award-number":["12071459","11991022","11771386","11728104"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["283106"],"award-info":[{"award-number":["283106"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,8]]},"DOI":"10.1007\/s10878-024-01193-z","type":"journal-article","created":{"date-parts":[[2024,7,28]],"date-time":"2024-07-28T12:01:36Z","timestamp":1722168096000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Maximizing stochastic set function under a matroid constraint from decomposition"],"prefix":"10.1007","volume":"48","author":[{"given":"Shengminjie","family":"Chen","sequence":"first","affiliation":[]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8441-7334","authenticated-orcid":false,"given":"Wenguo","family":"Yang","sequence":"additional","affiliation":[]},{"given":"Suixiang","family":"Gao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,28]]},"reference":[{"issue":"3","key":"1193_CR1","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.1287\/moor.2015.0766","volume":"41","author":"M Adamczyk","year":"2013","unstructured":"Adamczyk M, Sviridenko M, Ward J (2013) Submodular stochastic probing on matroids. Math Oper Res 41(3):1022\u20131038","journal-title":"Math Oper Res"},{"key":"1193_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal A, Assadi S, Khanna S (2019) Stochastic submodular cover with limited adaptivity. In: Proceedings of the 2019 annual ACM-SIAM symposium on discrete algorithms (SODA), pp 323\u2013342","DOI":"10.1137\/1.9781611975482.21"},{"key":"1193_CR3","doi-asserted-by":"publisher","first-page":"2374","DOI":"10.1287\/mnsc.2015.2254","volume":"62","author":"A Asadpour","year":"2016","unstructured":"Asadpour A, Nazerzadeh H (2016) Maximizing stochastic monotone submodular functions. Manag Sci 62:2374\u20132391","journal-title":"Manag Sci"},{"key":"1193_CR4","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu G, Chekuri C, Pal M, Vondr\u00e1k J (2011) Maximizing a monotone submodular function subject to a matroid constraint. SIAM J Comput 40:1740\u20131766","journal-title":"SIAM J Comput"},{"key":"1193_CR5","doi-asserted-by":"publisher","first-page":"1831","DOI":"10.1137\/110839655","volume":"43","author":"C Chekuri","year":"2014","unstructured":"Chekuri C, Vondr\u00e1k J, Zenklusen R (2014) Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J Comput 43:1831\u20131879","journal-title":"SIAM J Comput"},{"key":"1193_CR6","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.tcs.2020.12.041","volume":"857","author":"S Chen","year":"2021","unstructured":"Chen S, Yang W, Gao S, Jin R (2021) Novel algorithms for maximum DS decomposition. Theor Comput Sci 857:87\u201396","journal-title":"Theor Comput Sci"},{"key":"1193_CR7","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(84)90003-9","volume":"7","author":"M Conforti","year":"1984","unstructured":"Conforti M, Cornu\u00e9jols G (1984) Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Appl Math 7:251\u2013274","journal-title":"Discrete Appl Math"},{"key":"1193_CR8","unstructured":"Cui S, Han K, Zhu T, Tang J, Wu B, Huang H (2021) Randomized algorithms for submodular function maximization with a $$k$$-system constraint. In: Meila M, Zhang T (eds) Proceedings of the 38th international conference on machine learning, PMLR, Proceedings of machine learning research, vol 139, pp 2222\u20132232. https:\/\/proceedings.mlr.press\/v139\/cui21b.html"},{"key":"1193_CR9","doi-asserted-by":"publisher","unstructured":"Cui S, Han K, Tang J, Huang H (2023) Constrained subset selection from data streams for profit maximization. In: Proceedings of the ACM web conference 2023, WWW\u201923, pp 1822\u20131831. https:\/\/doi.org\/10.1145\/3543507.3583490","DOI":"10.1145\/3543507.3583490"},{"key":"1193_CR10","unstructured":"Esfandiari H, Karbasi A, Mirrokni V (2021) Adaptivity in adaptive submodularity. In: Proceedings of thirty fourth conference on learning theory, vol 134, pp 1823\u20131846"},{"key":"1193_CR11","doi-asserted-by":"crossref","unstructured":"Feldman M, Naor JS, Schwartz R (2011) A unified continuous greedy algorithm for submodular maximization. In: IEEE 52nd annual symposium on foundations of computer science, pp 570\u2013579","DOI":"10.1109\/FOCS.2011.46"},{"issue":"1","key":"1193_CR12","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"ML Fisher","year":"1978","unstructured":"Fisher ML, Nemhauser GL, Wolsey LA (1978) An analysis of approximations for maximizing submodular set functions-II. Math Program 8(1):73\u201387","journal-title":"Math Program"},{"key":"1193_CR13","doi-asserted-by":"crossref","unstructured":"Fukunaga T, Konishi T, Fujita S, Ki Kawarabayashi (2019) Stochastic submodular maximization with performance-dependent item costs. In: Proceedings of the AAAI conference on artificial intelligence, vol 33, pp 1485\u20131494","DOI":"10.1609\/aaai.v33i01.33011485"},{"key":"1193_CR14","unstructured":"Ghuge R, Gupta A, Nagarajan V (2021) The power of adaptivity for stochastic submodular cover. In: Proceedings of the 38th international conference on machine learning, vol 139, pp 3702\u20133712"},{"key":"1193_CR15","unstructured":"Golovin D, Krause A (2011) Adaptive submodular optimization under matroid constraints. CoRR abs\/1101.4450. arXiv:1101.4450"},{"key":"1193_CR16","first-page":"427","volume":"42","author":"D Golovin","year":"2012","unstructured":"Golovin D, Krause A (2012) Adaptive submodularity: theory and applications in active learning and stochastic optimization. J Artif Intell Res 42:427\u2013486","journal-title":"J Artif Intell Res"},{"key":"1193_CR17","unstructured":"Gotovos A, Karbasi A, Krause A (2015) Non-monotone adaptive submodular maximization. In: Proceedings of the 24th international conference on artificial intelligence, IJCAI\u201915, pp 1996\u20132003"},{"key":"1193_CR18","unstructured":"Harshaw C, Feldman M, Ward J, Karbasi A (2019) Submodular maximization beyond non-negativity: guarantees, fast algorithms, and applications. In: 36th International conference on machine learning, ICML 2019, pp 4684\u20134705"},{"issue":"4","key":"1193_CR19","doi-asserted-by":"publisher","first-page":"3315","DOI":"10.1137\/19M1304271","volume":"30","author":"H Hassani","year":"2020","unstructured":"Hassani H, Karbasi A, Mokhtari A, Shen Z (2020) Stochastic conditional gradient++: (non)convex minimization and continuous submodular maximization. SIAM J Optim 30(4):3315\u20133344","journal-title":"SIAM J Optim"},{"key":"1193_CR20","unstructured":"Iyer R, Bilmes J (2012) Algorithms for approximate minimization of the difference between submodular functions, with applications. In: Proceedings of the twenty-eighth conference on uncertainty in artificial intelligence, pp 407\u2013417"},{"issue":"10","key":"1193_CR21","doi-asserted-by":"publisher","first-page":"1756","DOI":"10.14778\/3467861.3467866","volume":"14","author":"T Jin","year":"2021","unstructured":"Jin T, Yang Y, Yang R, Shi J, Huang K, Xiao X (2021) Unconstrained submodular maximization with modular costs: tight approximation and application to profit maximization. Proc VLDB Endow 14(10):1756\u20131768. https:\/\/doi.org\/10.14778\/3467861.3467866","journal-title":"Proc VLDB Endow"},{"key":"1193_CR22","doi-asserted-by":"crossref","unstructured":"Joseph KJ, Vamshi Teja R, Singh K, Balasubramanian VN (2019) Submodular batch selection for training deep neural networks. In: Proceedings of the 28th international joint conference on artificial intelligence, pp 2677\u20132683","DOI":"10.24963\/ijcai.2019\/372"},{"key":"1193_CR23","unstructured":"Kazemi E, Minaee S, Feldman M, Karbasi A (2021) Regularized submodular maximization at scale. In: Proceedings of the 38th international conference on machine learning, vol 139, pp 5356\u20135366"},{"key":"1193_CR24","doi-asserted-by":"crossref","unstructured":"Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining, pp 137\u2013146","DOI":"10.1145\/956750.956769"},{"key":"1193_CR25","unstructured":"Lu C, Yang W, Gao S (2021) Regularized non-monotone submodular maximization. CoRR abs\/2103.10008. arXiv:2103.10008"},{"issue":"1","key":"1193_CR26","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions-I. Math Program 14(1):265\u2013294","journal-title":"Math Program"},{"key":"1193_CR27","doi-asserted-by":"publisher","unstructured":"Nikolakaki SM, Ene A, Terzi E (2021) An efficient framework for balancing submodularity and cost. In: Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, KDD\u201921, pp 1256\u20131266. https:\/\/doi.org\/10.1145\/3447548.3467367","DOI":"10.1145\/3447548.3467367"},{"key":"1193_CR28","unstructured":"Peng B, Chen W (2019) Adaptive influence maximization with myopic feedback. In: Proceedings of the 33rd international conference on neural information processing systems"},{"key":"1193_CR29","unstructured":"Tang S, Yuan J (2021) Adaptive regularized submodular maximization. In: 32nd International symposium on algorithms and computation (ISAAC 2021), vol 212, pp 69:1\u201369:13"},{"issue":"1","key":"1193_CR30","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1109\/TNET.2016.2563397","volume":"25","author":"G Tong","year":"2017","unstructured":"Tong G, Wu W, Tang S, Du DZ (2017) Adaptive influence maximization in dynamic social networks. IEEE\/ACM Trans Netw 25(1):112\u2013125","journal-title":"IEEE\/ACM Trans Netw"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01193-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01193-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01193-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T19:11:55Z","timestamp":1724440315000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01193-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,28]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["1193"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01193-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,7,28]]},"assertion":[{"value":"13 July 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"3"}}