{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:06:29Z","timestamp":1753884389583,"version":"3.41.2"},"reference-count":26,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"DOI":"10.13039\/501100007129","name":"Natural Science Foundation of Shandong Province","doi-asserted-by":"crossref","award":["ZR2022MA034","ZR2019MA022"],"award-info":[{"award-number":["ZR2022MA034","ZR2019MA022"]}],"id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"crossref"}]},{"name":"the Doctoral Research Foundation of Weifang University","award":["2017BS02"],"award-info":[{"award-number":["2017BS02"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Foundation of China","doi-asserted-by":"crossref","award":["12101587"],"award-info":[{"award-number":["12101587"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002858","name":"China Postdoctoral Science Foundation","doi-asserted-by":"crossref","award":["2022M720329"],"award-info":[{"award-number":["2022M720329"]}],"id":[{"id":"10.13039\/501100002858","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:p> We study the problem of maximizing a monotone non-submodular function under a [Formula: see text]-knapsack constraint on the integer lattice. We propose three streaming algorithms to approach this problem. We first design a two-pass [Formula: see text]-approximate algorithm with total memory complexity [Formula: see text], and total query complexity for each element [Formula: see text]. The algorithm relies on a binary search technique to determine the amount of the current elements to be added into the output solution. It also requires to have a good estimate of the optimal value, we use the maximum value of the unit standard vector which can be obtained by reading a round of data to construct a guess set of the optimal value. Then, we modify our algorithm to avoid a repetitive reading of data by dynamically update the maximum value of the unit vector along with the coming elements, and obtain a one-pass streaming algorithm with same approximate ratio. Moreover, we design an improved StreamingKnapsack algorithm to reduce the memory complexity to [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0217595923400183","type":"journal-article","created":{"date-parts":[[2023,6,10]],"date-time":"2023-06-10T05:24:06Z","timestamp":1686374646000},"source":"Crossref","is-referenced-by-count":0,"title":["Streaming Algorithms for Non-Submodular Functions Maximization with <i>d<\/i>-Knapsack Constraint on the Integer Lattice"],"prefix":"10.1142","volume":"40","author":[{"given":"Jingjing","family":"Tan","sequence":"first","affiliation":[{"name":"School of Mathematics and Information Science, Weifang University, Weifang 261061, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruiqi","family":"Yang","sequence":"additional","affiliation":[{"name":"Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yapu","family":"Zhang","sequence":"additional","affiliation":[{"name":"Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingyue","family":"Zhu","sequence":"additional","affiliation":[{"name":"Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2023,7,29]]},"reference":[{"key":"S0217595923400183BIB001","first-page":"671","author":"Badanidiyuru A","year":"2014","journal-title":"Proc. KDD"},{"key":"S0217595923400183BIB002","doi-asserted-by":"crossref","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"C\u0103linescu G","year":"2011","journal-title":"SIAM Journal of Computing"},{"key":"S0217595923400183BIB003","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/s10107-015-0900-7","volume":"154","author":"Chakrabarti A","year":"2015","journal-title":"Mathematical Programming"},{"key":"S0217595923400183BIB004","first-page":"303","author":"Chekuri C","year":"2019","journal-title":"Proc. SODA"},{"key":"S0217595923400183BIB005","first-page":"1057","author":"Das A","year":"2011","journal-title":"Proc. ICML"},{"key":"S0217595923400183BIB006","first-page":"439","author":"El-Arini K","year":"2011","journal-title":"Proc. ICKDDM"},{"key":"S0217595923400183BIB007","first-page":"274","author":"Ene A","year":"2019","journal-title":"Proc. SODA"},{"key":"S0217595923400183BIB008","first-page":"427","volume":"42","author":"Golovin D","year":"2011","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S0217595923400183BIB009","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1007\/s10898-019-00800-2","volume":"75","author":"Gong S","year":"2019","journal-title":"Journal of Global Optimization"},{"key":"S0217595923400183BIB010","first-page":"133","author":"Gottschalk C","year":"2015","journal-title":"Proc. WAOA"},{"key":"S0217595923400183BIB011","first-page":"438","author":"Huang C","year":"2019","journal-title":"Proc. WADS"},{"key":"S0217595923400183BIB012","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1007\/s11590-019-01430-z","volume":"14","author":"Jiang YJ","year":"2020","journal-title":"Optimization Letters"},{"key":"S0217595923400183BIB013","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1061\/(ASCE)0733-9496(2008)134:6(516)","volume":"134","author":"Krause A","year":"2008","journal-title":"Journal of Water Resources Planning and Management"},{"key":"S0217595923400183BIB014","first-page":"1216","author":"Kapralov M","year":"2012","journal-title":"Proc. SODA"},{"key":"S0217595923400183BIB015","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/956750.956769","author":"Kempe D","year":"2003","journal-title":"Proc. KDD"},{"key":"S0217595923400183BIB016","first-page":"1560","author":"Khanna R","year":"2017","journal-title":"Proc. ICAIS"},{"key":"S0217595923400183BIB017","first-page":"2791","author":"Kuhnle A","year":"2018","journal-title":"Proc. ICML"},{"key":"S0217595923400183BIB018","first-page":"3829","author":"Norouzi-Fard A","year":"2018","journal-title":"Proc. ICML"},{"key":"S0217595923400183BIB019","doi-asserted-by":"crossref","first-page":"1208","DOI":"10.1007\/s10878-020-00558-4","volume":"39","author":"Nong Q","year":"2020","journal-title":"Journal of Combinatorial Optimization"},{"key":"S0217595923400183BIB020","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S1793830909000063","volume":"1","author":"Shioura A","year":"2009","journal-title":"Discrete Mathematics, Algorithms and Applications"},{"key":"S0217595923400183BIB021","first-page":"351","author":"Soma T","year":"2014","journal-title":"Proc. ICML"},{"key":"S0217595923400183BIB022","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1007\/s10107-018-1324-y","volume":"172","author":"Soma T","year":"2018","journal-title":"Mathematical Programming"},{"key":"S0217595923400183BIB023","first-page":"67","author":"Vondr\u01cek J","year":"2008","journal-title":"Proc. STOC"},{"key":"S0217595923400183BIB024","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1007\/s10898-019-00840-8","volume":"76","author":"Wang YJ","year":"2020","journal-title":"Journal of Global Optimization"},{"key":"S0217595923400183BIB025","first-page":"195","volume":"36","author":"Yang RQ","year":"2019","journal-title":"Asia Pacific Journal of Operational Research"},{"key":"S0217595923400183BIB026","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1007\/s10898-021-01014-1","volume":"80","author":"Zhang ZN","year":"2021","journal-title":"Journal of Global Optimization"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595923400183","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T08:01:29Z","timestamp":1696406489000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0217595923400183"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,29]]},"references-count":26,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["10.1142\/S0217595923400183"],"URL":"https:\/\/doi.org\/10.1142\/s0217595923400183","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"type":"print","value":"0217-5959"},{"type":"electronic","value":"1793-7019"}],"subject":[],"published":{"date-parts":[[2023,7,29]]},"article-number":"2340018"}}