{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:58:55Z","timestamp":1753883935105,"version":"3.41.2"},"reference-count":22,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["11971349"],"award-info":[{"award-number":["11971349"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Humanities and Social Science Foundation of the Education of Ministry of China","award":["19YJC630188"],"award-info":[{"award-number":["19YJC630188"]}]},{"name":"Research Program of Tianjin Municipal Education Commission","award":["2017KJ242"],"award-info":[{"award-number":["2017KJ242"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:p> In this paper, the problem we study is how to maximize a monotone non-submodular function with cardinality constraint. Different from the previous streaming algorithms, this paper mainly considers the sliding window model. Based on the concept of diminishing-return ratio [Formula: see text], we propose a [Formula: see text]-approximation algorithm with the memory [Formula: see text], where [Formula: see text] is the ratio between maximum and minimum values of any singleton element of function [Formula: see text]. Then, we improve the approximation ratio to [Formula: see text] through the sub-windows at the expense of losing some memory. Our results generalize the corresponding results for the submodular case. <\/jats:p>","DOI":"10.1142\/s021759592150038x","type":"journal-article","created":{"date-parts":[[2021,7,20]],"date-time":"2021-07-20T10:27:12Z","timestamp":1626776832000},"source":"Crossref","is-referenced-by-count":0,"title":["Approximation Algorithms for Non-Submodular Optimization Over Sliding Windows"],"prefix":"10.1142","volume":"39","author":[{"given":"Yunxin","family":"Luo","sequence":"first","affiliation":[{"name":"Institute of Operations Research and Systems Engineering, College of Science, Tianjin, University of Technology, Tianjin 300384, P. R. China"}]},{"given":"Chenchen","family":"Wu","sequence":"additional","affiliation":[{"name":"Institute of Operations Research and Systems Engineering, College of Science, Tianjin, University of Technology, Tianjin 300384, P. R. China"}]},{"given":"Chunming","family":"Xu","sequence":"additional","affiliation":[{"name":"Institute of Operations Research and Systems Engineering, College of Science, Tianjin, University of Technology, Tianjin 300384, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2021,8,31]]},"reference":[{"key":"S021759592150038XBIB001","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509964"},{"key":"S021759592150038XBIB002","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187907"},{"key":"S021759592150038XBIB003","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623637"},{"key":"S021759592150038XBIB004","first-page":"498","volume-title":"Proceedings of The 34th International Conference on Machine Learning (ICML 2017)","author":"Bian AA","year":"2017"},{"key":"S021759592150038XBIB005","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.55"},{"key":"S021759592150038XBIB006","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.80"},{"key":"S021759592150038XBIB007","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398363"},{"key":"S021759592150038XBIB008","first-page":"4044","volume-title":"Proceedings of Neural Information Processing Systems","author":"Elenberg E","year":"2017"},{"key":"S021759592150038XBIB009","doi-asserted-by":"publisher","DOI":"10.21236\/ADA501771"},{"key":"S021759592150038XBIB010","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052699"},{"key":"S021759592150038XBIB011","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00458-4"},{"key":"S021759592150038XBIB012","first-page":"391","volume-title":"Proceedings of 27th International Conference on Machine Learning","author":"Gomes R","year":"2010"},{"key":"S021759592150038XBIB013","first-page":"36","volume":"8","author":"Gomez Rodriguez M","year":"2018","journal-title":"ACM Transactions on Knowledge Discovery from Data"},{"key":"S021759592150038XBIB014","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"S021759592150038XBIB015","first-page":"235","volume":"9","author":"Krause A","year":"2008","journal-title":"Journal of Machine Learning Research"},{"key":"S021759592150038XBIB016","first-page":"3311","volume-title":"Proceedings of the 36th International Conference on Machine Learning","author":"Kazemi E","year":"2019"},{"key":"S021759592150038XBIB017","first-page":"510","volume-title":"Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies","author":"Lin H","year":"2011"},{"key":"S021759592150038XBIB018","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.137"},{"key":"S021759592150038XBIB019","first-page":"2049","volume-title":"Proceedings of Neural Information Processing Systems","author":"Mirzasoleiman B","year":"2013"},{"key":"S021759592150038XBIB020","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"S021759592150038XBIB021","first-page":"3826","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Norouzi-Fard A","year":"2018"},{"key":"S021759592150038XBIB022","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-019-00840-8"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021759592150038X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T05:12:18Z","timestamp":1666415538000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S021759592150038X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,31]]},"references-count":22,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["10.1142\/S021759592150038X"],"URL":"https:\/\/doi.org\/10.1142\/s021759592150038x","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"type":"print","value":"0217-5959"},{"type":"electronic","value":"1793-7019"}],"subject":[],"published":{"date-parts":[[2021,8,31]]},"article-number":"2150038"}}