{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:05:21Z","timestamp":1753880721411,"version":"3.41.2"},"reference-count":42,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p> The field of Submodular Maximization subject to a Knapsack constraint has recently expanded to a variety of application domains, which is facing some challenges such as data explosions or additional conditions. There exist plenty of objective functions that cannot be evaluated exactly in many real cases unless they are estimated with errors. It leads to solving the problem under noise models. Somewhat surprisingly, Submodular Maximization subject to a Knapsack constraint under Noise models ([Formula: see text]) has never been discussed a lot before. Hence, in this paper, we consider the problem with two kinds of noise models which are addition and multiplication. Inspired by the traditional Greedy algorithm, we first propose a Greedy algorithm under Noises with provable theoretical bounds. In order to find the solution when input data are extremely large, we then devise an efficient streaming algorithm that scans only a single pass over the data and guarantees theoretical approximations. Finally, we conduct some experiments on Influence Maximization problem under knapsack constraint, an instance of [Formula: see text] to show the performances of the proposed algorithms. <\/jats:p>","DOI":"10.1142\/s0217595922500130","type":"journal-article","created":{"date-parts":[[2022,4,18]],"date-time":"2022-04-18T09:04:32Z","timestamp":1650272672000},"source":"Crossref","is-referenced-by-count":2,"title":["Submodular Maximization Subject to a Knapsack Constraint Under Noise Models"],"prefix":"10.1142","volume":"39","author":[{"given":"Dung T. K.","family":"Ha","sequence":"first","affiliation":[{"name":"Faculty of Information Technology, University of Engineering and Technology, Vietnam National University, Hanoi, 144 Xuan Thuy Street, Cau Giay District, Hanoi 10000, Vietnam"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Canh V.","family":"Pham","sequence":"additional","affiliation":[{"name":"ORLab, Faculty of Computer Science, Phenikaa University, Yen Nghia Ward, Ha Dong District, Hanoi, 12116, Vietnam"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huan X.","family":"Hoang","sequence":"additional","affiliation":[{"name":"Faculty of Information Technology, University of Engineering and Technology, Vietnam National University, Hanoi, 144 Xuan Thuy Street, Cau Giay District, Hanoi 10000, Vietnam"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2022,4,18]]},"reference":[{"issue":"3","key":"S0217595922500130BIB001","first-page":"636","volume":"71","author":"Amir R","year":"2005","journal-title":"Southern Economic Journal"},{"issue":"2","key":"S0217595922500130BIB002","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1561\/2200000039","volume":"6","author":"Bach FR","year":"2013","journal-title":"Foundations and Trends in Machine Learning"},{"key":"S0217595922500130BIB003","first-page":"671","volume-title":"th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, KDD \u201914","author":"Badanidiyuru A","year":"2014"},{"key":"S0217595922500130BIB004","first-page":"1497","volume-title":"Proc. Twenty-Fifth Annual ACM-SIAM Symp. Discrete Algorithms, SODA 2014","author":"Badanidiyuru A","year":"2014"},{"key":"S0217595922500130BIB005","first-page":"13","volume-title":"Proc. th ACM Symp. Parallelism in Algorithms and Architectures, SPAA 2017","author":"Bateni M","year":"2017"},{"key":"S0217595922500130BIB006","first-page":"946","volume-title":"Proc. Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014","author":"Borgs C","year":"2014"},{"key":"S0217595922500130BIB007","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"key":"S0217595922500130BIB008","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"S0217595922500130BIB009","first-page":"379","volume-title":"Proc. Eleventh SIAM Int. Conf. Data Mining, SDM 2011","author":"Chen W","year":"2011"},{"key":"S0217595922500130BIB010","series-title":"Synthesis Lectures on Data Management","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-01896-1","volume-title":"Information and Influence Propagation in Social Networks","author":"Chen W","year":"2013"},{"key":"S0217595922500130BIB011","first-page":"88","volume-title":"ICDM 2010, 10th IEEE Int. Conf. Data Mining","author":"Chen W","year":"2010"},{"key":"S0217595922500130BIB012","first-page":"629","volume-title":"Proc. 23rd ACM Int. Conf. Information and Knowledge Management","author":"Cohen E","year":"2014"},{"key":"S0217595922500130BIB013","series-title":"Proceedings of Machine Learning Research","first-page":"1426","volume-title":"Proc. th Int. Conf. Machine Learning, ICML 2019","volume":"97","author":"Crawford VG","year":"2019"},{"key":"S0217595922500130BIB014","first-page":"3:1","volume":"19","author":"Das A","year":"2018","journal-title":"Journal of Machine Learning Research"},{"key":"S0217595922500130BIB016","first-page":"391","volume-title":"Proc. 27th Int. Conf. Machine Learning (ICML-10)","author":"Gomes R","year":"2010"},{"key":"S0217595922500130BIB018","first-page":"3045","volume-title":"Advances in Neural Information Processing Systems 29: Annual Conf. Neural Information Processing Systems","author":"Horel T","year":"2016"},{"issue":"4","key":"S0217595922500130BIB019","doi-asserted-by":"crossref","first-page":"1006","DOI":"10.1007\/s00453-019-00628-y","volume":"82","author":"Huang C","year":"2020","journal-title":"Algorithmica"},{"key":"S0217595922500130BIB020","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"issue":"1","key":"S0217595922500130BIB021","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"Khuller S","year":"1999","journal-title":"Information Processing Letters"},{"key":"S0217595922500130BIB022","first-page":"235","volume":"9","author":"Krause A","year":"2008","journal-title":"Journal of Machine Learning Research"},{"key":"S0217595922500130BIB023","first-page":"1","volume-title":"25th ACM Symp. Parallelism in Algorithms and Architectures, SPAA \u201913","author":"Kumar R","year":"2013"},{"key":"S0217595922500130BIB024","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"issue":"3","key":"S0217595922500130BIB025","first-page":"511","volume":"80","author":"Milgrom P","year":"1990","journal-title":"The American Economic Review"},{"key":"S0217595922500130BIB026","series-title":"JMLR Workshop and Conference Proceedings","first-page":"1358","volume-title":"Proc. nd Int. Conf. Machine Learning, ICML 2016","volume":"48","author":"Mirzasoleiman B","year":"2016"},{"key":"S0217595922500130BIB027","first-page":"1812","volume-title":"Proc. Twenty-Ninth AAAI Conf. Artificial Intelligence","author":"Mirzasoleiman B","year":"2015"},{"key":"S0217595922500130BIB028","series-title":"Proceedings of Machine Learning Research","first-page":"3596","volume-title":"Proc. th Int. Conf. Machine Learning","volume":"80","author":"Mitrovic M","year":"2018"},{"key":"S0217595922500130BIB029","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"issue":"6","key":"S0217595922500130BIB030","doi-asserted-by":"crossref","first-page":"1084","DOI":"10.1109\/JSAC.2013.130610","volume":"31","author":"Nguyen H","year":"2013","journal-title":"IEEE Journal on Selected Areas in Communications"},{"key":"S0217595922500130BIB031","first-page":"695","volume-title":"Proc. 2016 Int. Conf. Management of Data, SIGMOD Conf. 2016","author":"Nguyen HT","year":"2016"},{"issue":"4","key":"S0217595922500130BIB032","doi-asserted-by":"crossref","first-page":"2419","DOI":"10.1109\/TNET.2017.2691544","volume":"25","author":"Nguyen HT","year":"2017","journal-title":"IEEE\/ACM Transactions on Networking"},{"key":"S0217595922500130BIB033","series-title":"Proceedings of Machine Learning Research","first-page":"3826","volume-title":"Proc. 35th Int. Conf. Machine Learning, ICML 2018","volume":"80","author":"Norouzi-Fard A","year":"2018"},{"issue":"4","key":"S0217595922500130BIB034","doi-asserted-by":"crossref","first-page":"694","DOI":"10.1109\/TEVC.2019.2929555","volume":"24","author":"Qian C","year":"2020","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"S0217595922500130BIB035","first-page":"3560","volume-title":"Advances in Neural Information Processing Systems 30: Annual Conf. Neural Information Processing Systems 2017","author":"Qian C","year":"2017"},{"key":"S0217595922500130BIB036","first-page":"394","volume-title":"Advances in Neural Information Processing Systems : Annual Conf. Neural Information Processing Systems 2018, NeurIPS","author":"Singer Y","year":"2018"},{"key":"S0217595922500130BIB037","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"key":"S0217595922500130BIB038","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723734"},{"key":"S0217595922500130BIB039","first-page":"75","volume-title":"Proc. ACM SIGMOD Int. Conf. Management of Data, SIGMOD","author":"Tang Y","year":"2014"},{"issue":"16","key":"S0217595922500130BIB040","doi-asserted-by":"crossref","first-page":"4165","DOI":"10.1016\/j.physa.2011.12.021","volume":"391","author":"Traud AL","year":"2012","journal-title":"Physica A: Statistical Mechanics and Its Applications"},{"key":"S0217595922500130BIB041","first-page":"67","volume-title":"Proc. 40th Annual ACM Symp. Theory of Computing","author":"Vondr\u00e1k J","year":"2008"},{"key":"S0217595922500130BIB042","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.3.410"},{"key":"S0217595922500130BIB043","first-page":"348","volume-title":"39th IEEE Int. Conf. Distributed Computing Systems, ICDCS 2019","author":"Yang R","year":"2019"},{"key":"S0217595922500130BIB044","first-page":"1295","volume-title":"IEEE Global Conf. Signal and Information Processing, GlobalSIP","author":"Yu Q","year":"2016"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595922500130","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T01:48:38Z","timestamp":1672105718000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0217595922500130"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,18]]},"references-count":42,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.1142\/S0217595922500130"],"URL":"https:\/\/doi.org\/10.1142\/s0217595922500130","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"type":"print","value":"0217-5959"},{"type":"electronic","value":"1793-7019"}],"subject":[],"published":{"date-parts":[[2022,4,18]]},"article-number":"2250013"}}