{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T01:44:23Z","timestamp":1778550263061,"version":"3.51.4"},"reference-count":19,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2019,8]]},"abstract":"<jats:p> We study a robust parameterized submodular function maximization inspired by [Mitrovi\u0107, S, I Bogunovic, A Norouzi-Fard and Jakub Tarnawski (2017). Streaming robust submodular maximization: A partitioned thresholding approach. In Proc. NIPS, pp. 4560\u20134569] and [Bogunovic, I, J Zhao and V Cevher (2018). Robust maximization of nonsubmodular objectives. In Proc. AISTATS, pp. 890\u2013899]. In our setting, given a parameterized set function, there are two additional twists. One is that elements arrive in a streaming style, and the other is that there are at most [Formula: see text] items deleted from the algorithm\u2019s memory when the stream is finished. The goal is to choose a robust set from the stream such that the robust ratio is maximized. We propose a two-phase algorithm for maximizing a normalized monotone robust parameterized submodular function with a cardinality constraint and show the robust ratio is close to a constant as [Formula: see text]. In the end, we empirically demonstrate the performance of our algorithm on deletion robust support selection problem. <\/jats:p>","DOI":"10.1142\/s0217595919500222","type":"journal-article","created":{"date-parts":[[2019,6,26]],"date-time":"2019-06-26T08:58:52Z","timestamp":1561539532000},"page":"1950022","source":"Crossref","is-referenced-by-count":7,"title":["Approximating Robust Parameterized Submodular Function Maximization in Large-Scales"],"prefix":"10.1142","volume":"36","author":[{"given":"Ruiqi","family":"Yang","sequence":"first","affiliation":[{"name":"Department of Operations Research and Scientific Computing, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing 100124, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[{"name":"Department of Operations Research and Scientific Computing, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing 100124, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanjun","family":"Jiang","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics Science, Ludong University, 186 Hongqi Middle Road, Zhifu District, Yantai, Shandong 264025, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yishui","family":"Wang","sequence":"additional","affiliation":[{"name":"Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, 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":[[2019,8,25]]},"reference":[{"key":"S0217595919500222BIB001","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623637"},{"key":"S0217595919500222BIB002","first-page":"498","volume-title":"Proceedings of the 34th International Conference on Machine Learning","author":"Bian AA","year":"2017"},{"key":"S0217595919500222BIB003","first-page":"508","volume-title":"Proceedings of the 34th International Conference on Machine Learning","author":"Bogunovic I","year":"2017"},{"key":"S0217595919500222BIB004","first-page":"890","volume-title":"Proceedings of the 21st International Conference on Artificial Intelligence and Statistics","author":"Bogunovic I","year":"2018"},{"key":"S0217595919500222BIB005","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.80"},{"key":"S0217595919500222BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0900-7"},{"key":"S0217595919500222BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_26"},{"key":"S0217595919500222BIB008","first-page":"1057","volume-title":"Proceedings of the 28th International Conference on International Conference on Machine Learning","author":"Das A","year":"2011"},{"key":"S0217595919500222BIB009","first-page":"4044","author":"Elenberg ER","year":"2017","journal-title":"Advances in Neural Information Processing Systems"},{"key":"S0217595919500222BIB011","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2011.5995589"},{"key":"S0217595919500222BIB012","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"S0217595919500222BIB014","first-page":"2761","volume":"9","author":"Krause A","year":"2008","journal-title":"Journal of Machine Learning Research"},{"key":"S0217595919500222BIB015","first-page":"1650","volume-title":"Proceedings of the 22nd AAAI Conference on Artificial Intelligence","author":"Krause A","year":"2007"},{"key":"S0217595919500222BIB016","first-page":"1379","volume-title":"Proceedings of the 32nd AAAI Conference on Artificial Intelligence","author":"Mirzasoleiman B","year":"2018"},{"key":"S0217595919500222BIB017","first-page":"4560","author":"Mitrovi\u0107 S","year":"2017","journal-title":"Advances in Neural Information Processing Systems"},{"key":"S0217595919500222BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"S0217595919500222BIB019","first-page":"3826","volume-title":"Proceedings of the 35th International Conference on Machine Learning","author":"Norouzi-Fard A","year":"2018"},{"key":"S0217595919500222BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-33461-5_26"},{"key":"S0217595919500222BIB021","first-page":"253","volume":"23","author":"Vondr\u00e1k J","year":"2010","journal-title":"RIMS Kokyuroku Bessatsu B"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595919500222","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,26]],"date-time":"2019-08-26T04:45:01Z","timestamp":1566794701000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0217595919500222"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8]]},"references-count":19,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2019,8,25]]},"published-print":{"date-parts":[[2019,8]]}},"alternative-id":["10.1142\/S0217595919500222"],"URL":"https:\/\/doi.org\/10.1142\/s0217595919500222","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8]]}}}