{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T16:31:49Z","timestamp":1754152309736,"version":"3.41.2"},"reference-count":29,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11871081"],"award-info":[{"award-number":["11871081"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Province Natural Science Foundation of Shandong","award":["ZR2022MA019","ZR2019MA061"],"award-info":[{"award-number":["ZR2022MA019","ZR2019MA061"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2025,8]]},"abstract":"<jats:p> We consider the problem of local privacy where actions are subsets of a ground multiset and expectation rewards are modeled by a [Formula: see text]decomposable monotone submodular function. For the DR-submodular maximization problem under a polymatroid constraint, Soma and Yoshida [26] provide a continuous greedy algorithm for no-privacy setting. In this paper, we obtain the first differentially private algorithm for DR-submodular maximization subject to a polymatroid constraint. Our algorithm achieves a [Formula: see text]approximation with a little loss and runs in [Formula: see text][Formula: see text] times where [Formula: see text] is the rank of the base polymatroid and [Formula: see text] is the size of ground set. Along the way, we analyze the utility and privacy of our algorithm. A concrete experiment to simulate the privacy Uber pickups location problem is provided, and our algorithm performs well within the agreed range. <\/jats:p>","DOI":"10.1142\/s0129054122460042","type":"journal-article","created":{"date-parts":[[2023,1,14]],"date-time":"2023-01-14T23:54:05Z","timestamp":1673740445000},"page":"649-666","source":"Crossref","is-referenced-by-count":0,"title":["A Differentially Private Approximation Algorithm for Submodular Maximization Under a Polymatroid Constraint Over the Integer Lattice"],"prefix":"10.1142","volume":"36","author":[{"given":"Jiaming","family":"Hu","sequence":"first","affiliation":[{"name":"Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing, 100124, P. R. China"}]},{"given":"Chunlin","family":"Hao","sequence":"additional","affiliation":[{"name":"Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing, 100124, P. R. China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2448-2158","authenticated-orcid":false,"given":"Cuixia","family":"Miao","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Qufu Normal University, Qufu, 273165, P. R. China"}]},{"given":"Bo","family":"Zhao","sequence":"additional","affiliation":[{"name":"Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing, 100124, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2023,1,14]]},"reference":[{"key":"S0129054122460042BIB001","first-page":"3400","volume-title":"Proc. 22nd Int. Conf. Artificial Intelligence and Statistics","author":"Agrawal R.","year":"2019"},{"key":"S0129054122460042BIB002","first-page":"644","volume-title":"Proc. 36th Inter. Conf. Machine Learning","author":"Bian Y.","year":"2019"},{"key":"S0129054122460042BIB003","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.106"},{"key":"S0129054122460042BIB004","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.16"},{"key":"S0129054122460042BIB005","first-page":"486","volume-title":"Advances in Neural Information Processing Systems","author":"Bian A.","year":"2017"},{"key":"S0129054122460042BIB006","first-page":"1650","volume-title":"Proc. 22nd Int. Conf. Artificial Intelligence and Statistics","author":"Cardoso A. R.","year":"2019"},{"key":"S0129054122460042BIB007","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i8.16860"},{"key":"S0129054122460042BIB008","first-page":"397","volume-title":"Proc. 21st Int. Conf. Algorithms and Architectures for Parallel Processing","author":"Cui Y.","year":"2021"},{"key":"S0129054122460042BIB009","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316389"},{"key":"S0129054122460042BIB010","doi-asserted-by":"publisher","DOI":"10.1137\/130920277"},{"issue":"3","key":"S0129054122460042BIB011","first-page":"265","volume":"7","author":"Dwork C.","year":"2016","journal-title":"J. Priv. Confidentiality"},{"key":"S0129054122460042BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-60033-8_35"},{"key":"S0129054122460042BIB013","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.90"},{"key":"S0129054122460042BIB014","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1110.1000"},{"key":"S0129054122460042BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-91434-9_6"},{"key":"S0129054122460042BIB016","doi-asserted-by":"publisher","DOI":"10.1109\/TrustCom53373.2021.00068"},{"key":"S0129054122460042BIB017","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.66"},{"key":"S0129054122460042BIB018","first-page":"2478","volume-title":"Proc. 34th Int. Conf. Machine Learning","author":"Mitrovic M.","year":"2017"},{"key":"S0129054122460042BIB019","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718508"},{"key":"S0129054122460042BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"S0129054122460042BIB021","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2022.3144084"},{"key":"S0129054122460042BIB022","first-page":"1279","volume-title":"Proc. 24th Int. Conf. Artificial Intelligence and Statistics","author":"Perez-Salazar S.","year":"2021"},{"volume-title":"ICML 2020 workshop on Negative Dependence and Submodularity for ML","year":"2020","author":"Sahin A.","key":"S0129054122460042BIB023"},{"key":"S0129054122460042BIB024","first-page":"8388","volume-title":"Proc. 37th Int. Conf. Machine Learning","author":"Sahin A.","year":"2020"},{"key":"S0129054122460042BIB026","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1324-y"},{"key":"S0129054122460042BIB027","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.08.012"},{"key":"S0129054122460042BIB028","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-05912-9_7"},{"key":"S0129054122460042BIB029","doi-asserted-by":"publisher","DOI":"10.1016\/j.cose.2019.101699"},{"key":"S0129054122460042BIB030","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-018-9483-x"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054122460042","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T03:44:28Z","timestamp":1753155868000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054122460042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,14]]},"references-count":29,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["10.1142\/S0129054122460042"],"URL":"https:\/\/doi.org\/10.1142\/s0129054122460042","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2023,1,14]]}}}