{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T17:28:48Z","timestamp":1761845328232,"version":"3.41.2"},"reference-count":19,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:p> Emerging applications such as optimal budget allocation and sensor placement impose problems of maximizing variants of submodular functions with constraints under a streaming setting. In this paper, we first devise a streaming algorithm based on Sieve-Streaming for maximizing a monotone diminishing return submodular (DR-submodular) function with a cardinality constraint on the integer lattice and show it is a one-pass algorithm with approximation ratio [Formula: see text]. The key idea to ensure one pass for the algorithm is to combine binary search for determining the level of an element with the exponential-growth method for estimating the OPT. Inspired by Sieve-Streaming++, we then improve the memory of the algorithm to [Formula: see text] and the query complexity to [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0217595921400042","type":"journal-article","created":{"date-parts":[[2021,2,2]],"date-time":"2021-02-02T13:11:33Z","timestamp":1612271493000},"source":"Crossref","is-referenced-by-count":7,"title":["Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice"],"prefix":"10.1142","volume":"38","author":[{"given":"Zhenning","family":"Zhang","sequence":"first","affiliation":[{"name":"Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing 100124, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Longkun","family":"Guo","sequence":"additional","affiliation":[{"name":"Shandong Key Laboratory of Computer Networks, School of Computer Science and Technology, Qilu University of Technology (Shandong Academy of Sciences), Jinan, Shandong 250353, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yishui","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Mathematics and Physics, University of Science and Technology Beijing, Beijing 100083, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[{"name":"Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing 100124, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dongmei","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2021,3,9]]},"reference":[{"key":"S0217595921400042BIB001","first-page":"1:1","volume-title":"Proc. ITCS","author":"Agrawal S","year":"2019"},{"key":"S0217595921400042BIB002","first-page":"671","volume-title":"Proc. KDD","author":"Badanidiyuru A","year":"2014"},{"key":"S0217595921400042BIB003","first-page":"283","volume-title":"Proc. SODA","author":"Balkanski E","year":"2019"},{"key":"S0217595921400042BIB004","first-page":"1202","volume-title":"Proc. SODA","author":"Buchbinder N","year":"2015"},{"key":"S0217595921400042BIB005","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"S0217595921400042BIB006","first-page":"274","volume-title":"Proc. SODA","author":"Ene A","year":"2019"},{"key":"S0217595921400042BIB007","first-page":"255","volume-title":"Proc. SODA","author":"Fahrbach M","year":"2019"},{"key":"S0217595921400042BIB008","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1137\/130920277","volume":"43","author":"Filmus Y","year":"2014","journal-title":"SIAM Journal of Computing"},{"key":"S0217595921400042BIB009","first-page":"438","volume-title":"Proc. WADS","author":"Huang C","year":"2019"},{"key":"S0217595921400042BIB010","first-page":"3311","volume-title":"Proc. ICML","author":"Kazemi E","year":"2019"},{"key":"S0217595921400042BIB011","first-page":"2791","volume-title":"Proc. ICML","author":"Kuhnle A","year":"2018"},{"key":"S0217595921400042BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"S0217595921400042BIB013","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"Nemhauser GL","year":"1978","journal-title":"Mathematical Programming Studies"},{"key":"S0217595921400042BIB014","first-page":"3829","volume-title":"Proc. ICML","author":"Norouzi-Fard A","year":"2018"},{"key":"S0217595921400042BIB015","first-page":"1395","volume-title":"Proc. AAAI","author":"Qian C","year":"2018"},{"key":"S0217595921400042BIB016","first-page":"351","volume-title":"Proc. ICML","author":"Soma T","year":"2014"},{"key":"S0217595921400042BIB017","first-page":"847","volume-title":"Proc. NIPS","author":"Soma T","year":"2015"},{"key":"S0217595921400042BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1324-y"},{"key":"S0217595921400042BIB019","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"Svirdenko M","year":"2004","journal-title":"Operations Research Letter"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595921400042","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T09:00:10Z","timestamp":1633942810000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0217595921400042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,9]]},"references-count":19,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["10.1142\/S0217595921400042"],"URL":"https:\/\/doi.org\/10.1142\/s0217595921400042","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"type":"print","value":"0217-5959"},{"type":"electronic","value":"1793-7019"}],"subject":[],"published":{"date-parts":[[2021,3,9]]},"article-number":"2140004"}}