{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T19:48:21Z","timestamp":1774727301989,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T00:00:00Z","timestamp":1770595200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T00:00:00Z","timestamp":1770595200000},"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,3]]},"DOI":"10.1007\/s10878-026-01395-7","type":"journal-article","created":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T18:58:53Z","timestamp":1770663533000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On maximizing k-submodular functions under p-system and d-knapsack constraints"],"prefix":"10.1007","volume":"51","author":[{"given":"Wenzhe","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shufang","family":"Gong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8958-3999","authenticated-orcid":false,"given":"Bin","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qian","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Priyanshi","family":"Garg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,9]]},"reference":[{"key":"1395_CR1","unstructured":"Badanidiyuru A, Karbasi A, Kazemi E, Vondr\u00e1k J (2020) Submodular maximization through barrier functions. In: 34th International Proceedings on NeurIPS, vol.\u00a033, pp. 524\u2013534. virtual"},{"key":"1395_CR2","doi-asserted-by":"crossref","unstructured":"Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A (2014) Streaming submodular maximization: massive data summarization on the fly. In: 20th International Proceedings on KDD, pp. 671\u2013680. ACM, New York, NY, USA","DOI":"10.1145\/2623330.2623637"},{"key":"1395_CR3","doi-asserted-by":"crossref","unstructured":"Badanidiyuru A, Vondr\u00e1k J (2014) Fast algorithms for maximizing submodular functions. In: 25th International Proceedings on SODA, pp. 1497\u20131514. SIAM, Portland, Oregon, USA","DOI":"10.1137\/1.9781611973402.110"},{"key":"1395_CR4","doi-asserted-by":"crossref","unstructured":"Buchbinder N, Feldman M, Garg M (2018) Deterministic (1\/2 + $$\\epsilon $$)-approximation for submodular maximization over a matroid. CoRR arXiv:1807.05532","DOI":"10.1137\/1.9781611975482.16"},{"issue":"3","key":"1395_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3309764","volume":"15","author":"N Buchbinder","year":"2015","unstructured":"Buchbinder N, Feldman M, Schwartz R (2015) Online submodular maximization with preemption. ACM Trans Algorithms 15(3):1\u201331","journal-title":"ACM Trans Algorithms"},{"issue":"1\u20132","key":"1395_CR6","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10107-015-0900-7","volume":"154","author":"A Chakrabarti","year":"2015","unstructured":"Chakrabarti A, Kale S (2015) Submodular maximization meets streaming: matchings, matroids, and more. Math Program 154(1\u20132):225\u2013247","journal-title":"Math Program"},{"key":"1395_CR7","unstructured":"Ene A, Nguyen HL (2022) Streaming algorithm for monotone $$k$$-submodular maximization with cardinality constraints. In: 39th International Proceedings on ICML, pp. 5944\u20135967. PMLR, Baltimore, Maryland, USA"},{"key":"1395_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121195","volume-title":"An analysis of approximations for maximizing submodular set functions-ii","author":"ML Fisher","year":"1978","unstructured":"Fisher ML, Nemhauser GL, Wolsey LA (1978) An analysis of approximations for maximizing submodular set functions-ii. Springer"},{"key":"1395_CR9","doi-asserted-by":"crossref","unstructured":"Gupta A, Roth A, Schoenebeck G, Talwar K (2010) Constrained non-monotone submodular maximization: Offline and secretary algorithms. In: 36th International Proceedings on WINE, pp. 246\u2013257. Springer, Stanford, CA, USA","DOI":"10.1007\/978-3-642-17572-5_20"},{"key":"1395_CR10","doi-asserted-by":"crossref","unstructured":"Huber A, Kolmogorov V (2012) Towards minimizing $$k$$-submodular functions. In: 2th International Proceedings on ISCO, pp. 451\u2013462. Springer, Athens, Greece","DOI":"10.1007\/978-3-642-32147-4_40"},{"key":"1395_CR11","doi-asserted-by":"crossref","unstructured":"Iwata S, ichi Tanigawa S, Yoshida Y (2015) Improved approximation algorithms for $$k$$-submodular function maximization. In: 27th International Proceedings on SODA, pp. 404\u2013413. SIAM, Arlington, VA, USA","DOI":"10.1137\/1.9781611974331.ch30"},{"key":"1395_CR12","unstructured":"Kazemi E, Mitrovic M, Zadimoghaddam M, Lattanzi S, Karbasi A (2019) Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. In: 36th International Proceedings on ICML, pp. 3311\u20133320. PMLR, Long Beach, California"},{"key":"1395_CR13","doi-asserted-by":"crossref","unstructured":"Kempe D, Kleinberg JM, Tardos \u00c9 (2003) Maximizing the spread of influence through a social network. In: 20th International Proceedings on KDD, pp. 137\u2013146. ACM, Washington, DC, USA","DOI":"10.1145\/956750.956769"},{"issue":"12","key":"1395_CR14","first-page":"2761","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause A, McMahan HB, Guestrin C, Gupta A (2008) Robust submodular observation selection. J Mach Learn Res 9(12):2761\u20132801","journal-title":"J Mach Learn Res"},{"key":"1395_CR15","unstructured":"Li W, Feldman M, Kazemi E, Karbasi A (2022) Submodular maximization in clean linear time. In: 36th International Proceedings on NeurIPS, pp. 7887\u20137897. New Orleans, LA, USA"},{"issue":"10","key":"1395_CR16","doi-asserted-by":"publisher","first-page":"1852","DOI":"10.1109\/TKDE.2018.2807843","volume":"30","author":"Y Li","year":"2018","unstructured":"Li Y, Fan J, Wang Y, Tan KL (2018) Influence maximization on social graphs: A survey. IEEE Trans Knowl Data Eng 30(10):1852\u20131872","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"1395_CR17","unstructured":"Mirzasoleiman B, Badanidiyuru A, Karbasi A (2016) Fast constrained submodular maximization: Personalized data summarization. In: 36th International Proceedings on ICML, pp. 1358\u20131367. JMLR.org, New York City, NY, USA"},{"issue":"3","key":"1395_CR18","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA (1978) Best algorithms for approximating the maximum of a submodular set function. Math Oper Res 3(3):177\u2013188","journal-title":"Math Oper Res"},{"issue":"1","key":"1395_CR19","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":"1395_CR20","unstructured":"Nguyen LN, Thai MT (2020) Streaming $$k$$-submodular maximization under noise subject to size constraint. In: 37th International Proceedings on ICML, pp. 7338\u20137347. PMLR, Virtual Event"},{"key":"1395_CR21","unstructured":"Ohsaka N, Yoshida Y (2015) Monotone $$k$$-submodular function maximization with size constraints. In: 28th International Proceedings on NIPS, pp. 7694\u2013702. Montreal, Quebec, Canada"},{"issue":"1\u20132","key":"1395_CR22","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/s10107-018-1320-2","volume":"172","author":"JB Orlin","year":"2018","unstructured":"Orlin JB, Schulz AS, Udwani R (2018) Robust monotone submodular function maximization. Math Program 172(1\u20132):505\u2013537","journal-title":"Math Program"},{"key":"1395_CR23","doi-asserted-by":"crossref","unstructured":"Oshima H (2016) Derandomization for $$k$$-submodular maximization. In: 28th International Proceedings on IWOCA, pp. 88\u201399. Springer, Newcastle, NSW, Australia","DOI":"10.1007\/978-3-319-78825-8_8"},{"issue":"1","key":"1395_CR24","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1007\/s10878-022-00858-x","volume":"44","author":"CV Pham","year":"2022","unstructured":"Pham CV, Vu QC, Ha DKT, Nguyen TT, Le ND (2022) Maximizing $$k$$-submodular functions under budget constraint: applications and streaming algorithms. J Comb Optim 44(1):723\u2013751","journal-title":"J Comb Optim"},{"issue":"4","key":"1395_CR25","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1109\/TEVC.2017.2749263","volume":"22","author":"C Qian","year":"2018","unstructured":"Qian C, Shi JC, Tang K, Zhou ZH (2018) Constrained monotone $$k$$-submodular function maximization using multiobjective evolutionary algorithms with theoretical guarantee. IEEE Trans Evol Comput 22(4):595\u2013608","journal-title":"IEEE Trans Evol Comput"},{"key":"1395_CR26","unstructured":"Rafiey A, Yoshida Y (2020) Fast and private submodular and $$ k $$-submodular functions maximization with matroid constraints. In: 28th International Proceedings on ICML, pp. 7887\u20137897. PMLR, Virtual Event"},{"key":"1395_CR27","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":"1395_CR28","unstructured":"Singh AP, Guillory A, Bilmes JA (2012) On bisubmodular maximization. In: 15th International Proceedings on AISTATS, pp. 1055\u20131063. JMLR.org, La Palma, Canary Islands,Spain"},{"key":"1395_CR29","doi-asserted-by":"crossref","unstructured":"Sun Y, Liu Y, Li M (2022) Maximization of $$k$$-submodular function with a matroid constraint. In: 16th International Proceedings on TAMC, pp. 156\u2013167. Springer, Tianjin, China","DOI":"10.1007\/978-3-031-20350-3_1"},{"issue":"1","key":"1395_CR30","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko M (2004) A note on maximizing a submodular set function subject to a knapsack constraint. Oper Res Lett 32(1):41\u201343","journal-title":"Oper Res Lett"},{"issue":"1","key":"1395_CR31","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":"1395_CR32","unstructured":"Wang B, Zhou H (2021) Multilinear extension of $$k$$-submodular functions. arXiv:2107.07103"},{"key":"1395_CR33","doi-asserted-by":"crossref","unstructured":"Ward J, Zivn\u00fd S (2014) Maximizing bisubmodular and $$k$$-submodular functions. In: 16th International Proceedings on SODA, pp. 1468\u20131481. SIAM, Portland, Oregon, USA","DOI":"10.1137\/1.9781611973402.108"},{"issue":"4","key":"1395_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2850419","volume":"12","author":"J Ward","year":"2014","unstructured":"Ward J, Zivn\u00fd S (2014) Maximizing $$k$$-submodular functions and beyond. ACM Trans Algorithms 12(4):1\u201326","journal-title":"ACM Trans Algorithms"},{"issue":"3","key":"1395_CR35","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1287\/moor.7.3.410","volume":"7","author":"LA Wolsey","year":"1982","unstructured":"Wolsey LA (1982) Maximising real-valued submodular functions: Primal and dual heuristics for location problems. Math Oper Res 7(3):410\u2013425","journal-title":"Math Oper Res"},{"issue":"3","key":"1395_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10878-023-01021-w","volume":"45","author":"K Yu","year":"2023","unstructured":"Yu K, Li M, Zhou Y, Liu Q (2023) On maximizing monotone or non-monotone $$k$$-submodular functions with the intersection of knapsack and matroid constraints. J Comb Optim 45(3):1\u201321","journal-title":"J Comb Optim"},{"key":"1395_CR37","doi-asserted-by":"crossref","unstructured":"Zhang Y, Li M, Yang D, Xue G (2019) A budget feasible mechanism for $$k$$-topic influence maximization in social networks. In: 19th International Proceedings on GLOBECOM, pp. 1\u20136. IEEE, Waikoloa, HI, USA","DOI":"10.1109\/GLOBECOM38437.2019.9013859"},{"key":"1395_CR38","doi-asserted-by":"crossref","unstructured":"Zheng L, Chan H, Loukides G, Li M (2021) Maximizing approximately $${k}$$-submodular functions. In: 15th International Proceedings on SIAM, pp. 414\u2013422. SIAM, Virtual Event","DOI":"10.1137\/1.9781611976700.47"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01395-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-026-01395-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01395-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T18:59:44Z","timestamp":1774724384000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-026-01395-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,9]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["1395"],"URL":"https:\/\/doi.org\/10.1007\/s10878-026-01395-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,9]]},"assertion":[{"value":"15 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 February 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"18"}}