{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T17:03:27Z","timestamp":1784999007906,"version":"3.55.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T00:00:00Z","timestamp":1784937600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T00:00:00Z","timestamp":1784937600000},"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":["12471306"],"award-info":[{"award-number":["12471306"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007129","name":"Natural Science Foundation of Shandong Province","doi-asserted-by":"publisher","award":["ZR2024MA031"],"award-info":[{"award-number":["ZR2024MA031"]}],"id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100012226","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":[[2026,8]]},"DOI":"10.1007\/s10878-026-01444-1","type":"journal-article","created":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T16:56:39Z","timestamp":1784998599000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic algorithms for k-submodular maximization with the chance constraint"],"prefix":"10.1007","volume":"52","author":[{"given":"Shufang","family":"Gong","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qiao","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8958-3999","authenticated-orcid":false,"given":"Bin","family":"Liu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,25]]},"reference":[{"issue":"2\u20133","key":"1444_CR1","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0166-218X(99)00103-1","volume":"93","author":"AA Ageev","year":"1999","unstructured":"Ageev AA, Sviridenko MI (1999) An 0.828-approximation algorithm for the uncapacitated facility location problem. Discret Appl Math 93(2\u20133):149\u2013156","journal-title":"Discret Appl Math"},{"key":"1444_CR2","doi-asserted-by":"crossref","unstructured":"Bao WX, Hang JY, Zhang ML (2022) Submodular feature selection for partial label learning. In: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Washington, DC, USA, pp 26\u201334","DOI":"10.1145\/3534678.3539292"},{"key":"1444_CR3","doi-asserted-by":"crossref","unstructured":"Chen J, Maehara T (2019) Chance-constrained submodular knapsack problem. In: Proceedings of the 25th International Computing and Combinatorics Conference. Xi\u2019an, China, pp 103\u2013114","DOI":"10.1007\/978-3-030-26176-4_9"},{"key":"1444_CR4","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0167-5060(08)70732-5","volume":"1","author":"G Cornuejols","year":"1977","unstructured":"Cornuejols G, Fisher M, Nemhauser GL (1977) On the uncapacitated location problem. Ann Discret Math 1:163\u2013177","journal-title":"Ann Discret Math"},{"key":"1444_CR5","doi-asserted-by":"crossref","unstructured":"Doerr B, Doerr C, Neumann A et al (2020) Optimization of chance-constrained submodular functions. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence, New York, NY, USA (Vol. 34, No. 02, pp. 1460-1467)","DOI":"10.1609\/aaai.v34i02.5504"},{"issue":"4","key":"1444_CR6","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U (1998) A threshold of ln n for approximating set cover. J ACM 45(4):634\u2013652","journal-title":"J ACM"},{"issue":"6","key":"1444_CR7","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6):1115\u20131145","journal-title":"J ACM"},{"key":"1444_CR8","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2023.106452","volume":"161","author":"DTK Ha","year":"2024","unstructured":"Ha DTK, Pham CV, Tran TD (2024) Improved approximation algorithms for $$k$$-submodular maximization under a knapsack constraint. Comput Oper Res 161:106452","journal-title":"Comput Oper Res"},{"issue":"6","key":"1444_CR9","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","volume":"33","author":"T Hagerup","year":"1990","unstructured":"Hagerup T, Rub C (1990) A guided tour of Chernoff bounds. Inf Process Lett 33(6):305\u2013308","journal-title":"Inf Process Lett"},{"key":"1444_CR10","unstructured":"Halperin E, Zwick U (2001) Combinatorial approximation algorithms for the maximum directed cut problem. Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms. Washington, DC, USA, pp 1\u20137"},{"issue":"3","key":"1444_CR11","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum DS (1982) Approximation algorithms for the set covering and vertex cover problems. SIAM J Comput 11(3):555\u2013556","journal-title":"SIAM J Comput"},{"key":"1444_CR12","doi-asserted-by":"crossref","unstructured":"Iwata S, Tanigawa S, Yoshida Y (2016) Improved approximation algorithms for $$k$$-submodular function maximization. In: Proceedings of the 27th annual ACM-SIAM symposium on Discrete algorithms. Arlington, VA, USA, pp 404\u2013413","DOI":"10.1137\/1.9781611974331.ch30"},{"issue":"2","key":"1444_CR13","first-page":"235","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause A, Singh A, Guestrin C (2008) Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies. J Mach Learn Res 9(2):235","journal-title":"J Mach Learn Res"},{"key":"1444_CR14","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.ress.2018.11.010","volume":"183","author":"C Malings","year":"2019","unstructured":"Malings C, Pozzi M (2019) Submodularity issues in value-of-information-based sensor placement. Reliab Eng Syst Saf 183:93\u2013103","journal-title":"Reliab Eng Syst Saf"},{"key":"1444_CR15","doi-asserted-by":"crossref","unstructured":"Mehrotra A, Vishnoi NK (2023) Maximizing submodular functions for recommendation in the presence of biases. In: Proceedings of the 32nd ACM Web Conference. Austin, TX, USA, pp 3625\u20133636","DOI":"10.1145\/3543507.3583195"},{"key":"1444_CR16","unstructured":"Nie G, Zhu Y, Nadew YY et al (2023) Size-constrained $$k$$-submodular maximization in near-linear time. In: Proceedings of the 39th Conference on Uncertainty in Artificial Intelligence, Pittsburgh, PA, USA, 1545\u20131554"},{"key":"1444_CR17","unstructured":"Ohsaka N, Yoshida Y (2018) Monotone $$k$$-submodular function maximization with size constraints. Proceedings of the 29th Neural Information Processing Systems, Montreal, Quebec, Canada, 32(1)"},{"key":"1444_CR18","unstructured":"Rafiey A, Yoshida Y (2020) Fast and private submodular and $$k$$-submodular functions maximization with matroid constraints. In: Proceedings of the 37th International Conference on Machine Learning, Virtual Event. pp 7887\u20137897"},{"key":"1444_CR19","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.disopt.2017.01.003","volume":"23","author":"S Sakaue","year":"2017","unstructured":"Sakaue S (2017) On maximizing a monotone $$k$$-submodular function subject to a matroid constraint. Discret Optim 23:105\u2013113","journal-title":"Discret Optim"},{"key":"1444_CR20","doi-asserted-by":"crossref","unstructured":"Sun Y, Liu Y, Li M (2022) Maximization of $$k$$-submodular function with a matroid constraint. In: Proceedings of the 17th International Conference on Theory and Applications of Models of Computation. Tianjin, China, pp 1\u201310","DOI":"10.1007\/978-3-031-20350-3_1"},{"key":"1444_CR21","doi-asserted-by":"crossref","unstructured":"Tang S (2018) When social advertising meets viral marketing: Sequencing social advertisements for influence maximization. Proceedings of the 32nd AAAI Conference on Artificial Intelligence, New Orleans, LA, USA, 32(1)","DOI":"10.1609\/aaai.v32i1.11306"},{"issue":"1","key":"1444_CR22","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.orl.2021.11.010","volume":"50","author":"Z Tang","year":"2022","unstructured":"Tang Z, Wang C, Chan H (2022) On maximizing a monotone $$k$$-submodular function under a knapsack constraint. Oper Res Lett 50(1):28\u201331","journal-title":"Oper Res Lett"},{"key":"1444_CR23","doi-asserted-by":"crossref","unstructured":"Tang Z, Chen J, Wang C (2023) An improved analysis of the greedy+ singleton algorithm for $$k$$-submodular knapsack maximization. In: Proceedings of the 17th International Joint Conference, Macau, China, 15\u201328","DOI":"10.1007\/978-3-031-39344-0_2"},{"issue":"4","key":"1444_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2850419","volume":"12","author":"J Ward","year":"2016","unstructured":"Ward J, \u017divn\u00fd S (2016) Maximizing $$k$$-submodular functions and beyond. ACM Trans Algorithms 12(4):1\u201326","journal-title":"ACM Trans Algorithms"},{"key":"1444_CR25","doi-asserted-by":"crossref","unstructured":"Xiao H, Liu Q, Zhou Y (2024) Approximation algorithms for k-submodular maximization subject to a knapsack constraint. J Oper Res Soc China 1\u201316","DOI":"10.1007\/s40305-024-00539-y"},{"key":"1444_CR26","doi-asserted-by":"crossref","unstructured":"Yan X, Do AV, Shi F (2023) Optimizing Chance-Constrained Submodular Problems with Variable Uncertainties. In: Proceedings of the 26th European Conference on Artificial Intelligence. Krak\u00f3w, Poland, pp 2826\u20132833","DOI":"10.3233\/FAIA230594"},{"key":"1444_CR27","doi-asserted-by":"crossref","unstructured":"Zhang Y, Li M, Yang D et al (2019) A budget feasible mechanism for $$k$$-topic influence maximization in social networks. In: 2019 IEEE Global Communications Conference, Waikoloa, HI, USA, 1\u20136","DOI":"10.1109\/GLOBECOM38437.2019.9013859"},{"key":"1444_CR28","unstructured":"Zhou H, Huang L, Wang B (2025) Improved Approximation Algorithms for $$k$$-Submodular Maximization via Multilinear Extension. In: Proceedings of the 13th International Conference on Learning Representations. Singapore"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01444-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-026-01444-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01444-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T16:56:42Z","timestamp":1784998602000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-026-01444-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,25]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,8]]}},"alternative-id":["1444"],"URL":"https:\/\/doi.org\/10.1007\/s10878-026-01444-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,25]]},"assertion":[{"value":"10 December 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors have no conflict of interest to declare that are relevant to the content of the paper.","order":1,"name":"Ethics","label":"Conflict of interest","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"5"}}