{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T01:59:28Z","timestamp":1781056768911,"version":"3.54.1"},"reference-count":32,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","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":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2026,8]]},"abstract":"<jats:p>In numerous real-world scenarios, the objective is to choose multiple sets of disjoint elements rather than just one. Thus a k-submodular function, which is a natural extension of a submodular function, finds applications in a wide array of contexts. This research is driven by a scenario in which data items within a stream are categorized into distinct groups, each subject to a size constraint. Firstly, we present a multi-pass streaming algorithm that needs [Formula: see text] passes through the data stream. This algorithm achieves a [Formula: see text]-approximation for the monotone case and a [Formula: see text]-approximation for the non-monotone case, respectively, for any constant [Formula: see text]. The query complexity is [Formula: see text], and the memory complexity is [Formula: see text]. And then we propose a one-pass streaming algorithm which returns a [Formula: see text]-approximation ratio for the monotone case and a [Formula: see text]-approximation ratio for the non-monotone case. The query complexity is [Formula: see text], and the memory complexity is [Formula: see text].<\/jats:p>","DOI":"10.1142\/s0129054125400106","type":"journal-article","created":{"date-parts":[[2025,8,14]],"date-time":"2025-08-14T03:28:43Z","timestamp":1755142123000},"page":"653-672","source":"Crossref","is-referenced-by-count":0,"title":["Streaming Algorithms for Maximizing\n                    <i>k<\/i>\n                    -Submodular Functions under a Partition Matroid Constraint"],"prefix":"10.1142","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-1850-9485","authenticated-orcid":false,"given":"Xinyu","family":"Zhang","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences, Ocean University of China, Qingdao 266100, P. R. China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8958-3999","authenticated-orcid":false,"given":"Bin","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Ocean University of China, Qingdao 266100, P. R. China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2025,8,13]]},"reference":[{"key":"S0129054125400106BIB001","first-page":"1","volume-title":"Proc. Int. Colloquium on Automata, Languages, and Programming","author":"Alaluf N.","year":"2020"},{"key":"S0129054125400106BIB002","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1145\/2623330.2623637","volume-title":"Proc. ACM SIGKDD Int. Conference on Knowledge Discovery and Data Mining","author":"Badanidiyuru A.","year":"2014"},{"key":"S0129054125400106BIB003","first-page":"1497","volume-title":"Proc. ACM-SIAM Symposium on Discrete Algorithms","author":"Badanidiyuru A.","year":"2014"},{"key":"S0129054125400106BIB004","first-page":"182","volume-title":"Proc. Int. Conference on Integer Programming and Combinatorial Optimization","author":"Calinescu G.","year":"2007"},{"key":"S0129054125400106BIB005","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/s10107-015-0900-7","volume":"154","author":"Chakrabarti A.","year":"2015","journal-title":"Math. Program."},{"key":"S0129054125400106BIB006","first-page":"1204","volume-title":"Proc. ACM-SIAM Symposium on Discrete Algorithms","author":"Chan T. H.","year":"2017"},{"key":"S0129054125400106BIB007","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1007\/978-3-662-47672-7_26","volume-title":"Proc. Int. Colloquium on Automata, Languages, and Programming","author":"Chekuri C.","year":"2015"},{"key":"S0129054125400106BIB008","first-page":"730","volume-title":"Proc. Int. Conference on Neural Information Processing Systems","author":"Feldman M.","year":"2018"},{"key":"S0129054125400106BIB009","first-page":"1","volume-title":"Proc. Int. Colloquium on Automata, Languages, and Programming","author":"Feldman M.","year":"2022"},{"key":"S0129054125400106BIB010","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1137\/1.9781611974331.ch30","volume-title":"Proc. ACM-SIAM Symposium on Discrete Algorithms","author":"Iwata S.","year":"2016"},{"key":"S0129054125400106BIB011","first-page":"3311","volume-title":"Proc. Int. Conference on Machine Learning","author":"Kazemi E.","year":"2019"},{"key":"S0129054125400106BIB012","volume-title":"Combinatorial Optimization","author":"Korte B. H.","year":"2011"},{"key":"S0129054125400106BIB013","first-page":"912","volume-title":"Proc. Conference of the North American Chapter of the Association for Computational Linguistics","author":"Lin H.","year":"2010"},{"key":"S0129054125400106BIB014","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"Nemhauser G. L.","year":"1978","journal-title":"Math. Program."},{"key":"S0129054125400106BIB015","first-page":"7338","volume-title":"Proc. Int. Conference on Machine Learning","author":"Nguyen L.","year":"2020"},{"key":"S0129054125400106BIB016","unstructured":"S. Niu, Q. Liu, Y. Zhou and M. Li, Fast algorithms for k-submodular maximization subject to a matroid constraint,\n                      arXiv.2307.13996\n                      (2023)."},{"key":"S0129054125400106BIB017","first-page":"116","volume-title":"Proc. Int. Conference on Neural Information Processing Systems","author":"Ohsaka N.","year":"2015"},{"key":"S0129054125400106BIB018","first-page":"88","volume-title":"Proc. Int. Workshop on Combinatorial Algorithms","author":"Oshima H.","year":"2017"},{"key":"S0129054125400106BIB019","first-page":"1","volume-title":"Proc. IEEE Int. Conference on Data Science and Advanced Analytics (DSAA)","author":"Pham C. V.","year":"2022"},{"issue":"1","key":"S0129054125400106BIB020","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1007\/s10878-022-00858-x","volume":"44","author":"Pham C. V.","year":"2022","journal-title":"J. Comb. Optim."},{"issue":"4","key":"S0129054125400106BIB021","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1109\/TEVC.2017.2749263","volume":"22","author":"Qian C.","year":"2017","journal-title":"IEEE. T. Evolut. Comput."},{"key":"S0129054125400106BIB022","first-page":"3","volume":"82","author":"Queyranne M.","year":"1998","journal-title":"Math. Program."},{"key":"S0129054125400106BIB023","first-page":"7887","volume-title":"Proc. Int. Conference on Machine Learning","author":"Rafiey A.","year":"2020"},{"key":"S0129054125400106BIB024","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/j.disopt.2017.01.003","volume":"23","author":"Sakaue S.","year":"2017","journal-title":"Discrete. Optim."},{"key":"S0129054125400106BIB025","first-page":"1055","volume-title":"Proc. Int. Conference on Artificial Intelligence and Statistics","author":"Singh A.","year":"2012"},{"key":"S0129054125400106BIB026","first-page":"351","volume-title":"Proc. Int. Conference on Machine Learning","author":"Soma T.","year":"2014"},{"key":"S0129054125400106BIB027","first-page":"1","volume-title":"Proc. Int. Conference on Theory and Applications of Models of Computation","author":"Sun Y.","year":"2022"},{"key":"S0129054125400106BIB028","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"issue":"1","key":"S0129054125400106BIB029","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.orl.2021.11.010","volume":"50","author":"Tang Z.","year":"2022","journal-title":"Oper. Res. Lett."},{"key":"S0129054125400106BIB030","doi-asserted-by":"crossref","first-page":"1340","DOI":"10.1145\/3442381.3449799","volume-title":"Proc. Web Int. Conference 2021","author":"Wang Y.","year":"2021"},{"issue":"4","key":"S0129054125400106BIB031","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2850419","volume":"12","author":"Ward J.","year":"2016","journal-title":"ACM. T. Algorithms."},{"key":"S0129054125400106BIB032","doi-asserted-by":"crossref","first-page":"100670","DOI":"10.1016\/j.disopt.2021.100670","volume":"42","author":"Yu Q.","year":"2021","journal-title":"Discrete. Optim."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054125400106","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T01:14:02Z","timestamp":1781054042000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054125400106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,13]]},"references-count":32,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2026,8]]}},"alternative-id":["10.1142\/S0129054125400106"],"URL":"https:\/\/doi.org\/10.1142\/s0129054125400106","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,13]]}}}