{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:09Z","timestamp":1740122409445,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T00:00:00Z","timestamp":1655942400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T00:00:00Z","timestamp":1655942400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Beijing Natural Science Foundation Project","award":["Z200002"],"award-info":[{"award-number":["Z200002"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12131003"],"award-info":[{"award-number":["12131003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Science and Technology Program of Beijing Education Commission","award":["KM201810005006"],"award-info":[{"award-number":["KM201810005006"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12001025"],"award-info":[{"award-number":["12001025"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s10878-022-00875-w","type":"journal-article","created":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T16:36:27Z","timestamp":1656002187000},"page":"3212-3232","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Private non-monotone submodular maximization"],"prefix":"10.1007","volume":"44","author":[{"given":"Xin","family":"Sun","sequence":"first","affiliation":[]},{"given":"Gaidi","family":"Li","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5122-4854","authenticated-orcid":false,"given":"Yapu","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Zhenning","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,23]]},"reference":[{"key":"875_CR1","doi-asserted-by":"crossref","unstructured":"Abadi M, Chu A, Goodfellow I, McMahan HB, Mironov I, Talwar K, Zhang L (2016) Deep learning with differential privacy. In Proceedings of the 23rd ACM SIGSAC Conference on Computer and Communications Security, p 308-318","DOI":"10.1145\/2976749.2978318"},{"issue":"2\/3","key":"875_CR2","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0166-218X(99)00103-1","volume":"93","author":"A Ageev","year":"1999","unstructured":"Ageev A, Sviridenko M (1999) An $$0.828$$ approximation algorithm for the uncapacitated facility location problem. Discrete Appl Math 93(2\/3):149\u2013156","journal-title":"Discrete Appl Math"},{"key":"875_CR3","unstructured":"Alon N, Spencer JH (2004) The probabilistic method. John Wiley & Sons 3:307\u2013314"},{"issue":"1","key":"875_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2907052","volume":"13","author":"P Austrin","year":"2016","unstructured":"Austrin P, Benabbas S, Georgiou K (2016) Better balance by being biased: A $$0.8776$$-approximation for max bisection. The ACM Transactions on Algorithms 13(1):1\u201327","journal-title":"The ACM Transactions on Algorithms"},{"issue":"2\u20133","key":"875_CR5","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1561\/2200000039","volume":"6","author":"FR Bach","year":"2013","unstructured":"Bach FR (2013) Learning with submodular functions: a convex optimization perspective. Foundations and Trends in Machine Learning 6(2\u20133):145\u2013373","journal-title":"Foundations and Trends in Machine Learning"},{"key":"875_CR6","doi-asserted-by":"crossref","unstructured":"Bu ZQ, Gopi S, Kulkarni J, Lee YT, Shen JH (2021) Tantipongpipat U. Fast and memory efficient differentially private-SGD via JL projections. In arXiv: 2102.03013","DOI":"10.29012\/jpc.780"},{"key":"875_CR7","doi-asserted-by":"crossref","unstructured":"Buchbinder N, Feldman M, Naor JS, Schwart R (2014) Submodular maximization with cardinality constraints. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, p 1433-1452","DOI":"10.1137\/1.9781611973730.80"},{"issue":"6","key":"875_CR8","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G C\u0103linescu","year":"2011","unstructured":"C\u0103linescu G, Chekuri C, P\u00e1l M, Vondr\u00e1k J (2011) Maximizing a monotone submodular function subject to a matroid constraint. SIAM J Comput 40(6):1740\u20131766","journal-title":"SIAM J Comput"},{"key":"875_CR9","doi-asserted-by":"crossref","unstructured":"Chekuri C, Jayram T S, Vondr\u00e1k J (2015) On multiplicative weight updates for concave and submodular function maximization. In Proceedings of the 6th Innovations in Theoretical Computer Science, p 201-210","DOI":"10.1145\/2688073.2688086"},{"issue":"3","key":"875_CR10","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/S0097539700382820","volume":"35","author":"C Chekuri","year":"2005","unstructured":"Chekuri C, Khanna S (2005) A polynomial time approximation scheme for the multiple knapsack problem. In SIAM J Comput 35(3):713\u2013728","journal-title":"In SIAM J Comput"},{"key":"875_CR11","unstructured":"Chekuri C, Vondr\u00e1k J, Zenklusen R (2010) Dependent randomized rounding for matroid polytopes and applications. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science, p 575-584"},{"key":"875_CR12","unstructured":"Das A, Kempe D (2011) Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In Proceedings of the 28th International Conference on International Conference on Machine Learning, p 1057-1064"},{"key":"875_CR13","doi-asserted-by":"crossref","unstructured":"Dwork C, Kenthapadi K, McSherry G, Mironov I, Naor M (2006) Our data, ourselves: Privacy via distributed noise generation. In Proceedings of the 25th Annual International Conference on the Theory and Applications of Cryptographic Technique, p 486-503","DOI":"10.1007\/11761679_29"},{"key":"875_CR14","doi-asserted-by":"crossref","unstructured":"Ene A, Nguyen HL (2016) Constrained submodular maximization: Beyond $$1\/e$$. In Proceedings of the 57th Annual Symposium on Foundations of Computer Science p 248-257","DOI":"10.1109\/FOCS.2016.34"},{"issue":"4","key":"875_CR15","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U (1998) A threshold of ln n for approximating set cover. Journal of the ACM 45(4):634\u2013652","journal-title":"Journal of the ACM"},{"issue":"4","key":"875_CR16","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige U, Mirrokni VS, Vondr\u00e1k J (2011) Maximizing non-monotone submodular functions. SIAM J Comput 40(4):1133\u20131153","journal-title":"SIAM J Comput"},{"key":"875_CR17","doi-asserted-by":"crossref","unstructured":"Feldman M, Naor J, Schwartz R (2011) A unified continuous greedy algorithm for submodular maximization. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, p 570-579","DOI":"10.1109\/FOCS.2011.46"},{"key":"875_CR18","doi-asserted-by":"crossref","unstructured":"Gharan SO, Vondr\u00e1k J (2011) Submodular maximization by simulated annealing. In Proceedings of the 22 Annual ACM-SIAM Symposium on Discrete Algorithms, p 1098-1116","DOI":"10.1137\/1.9781611973082.83"},{"issue":"6","key":"875_CR19","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42(6):1115\u20131145","journal-title":"Journal of the ACM"},{"key":"875_CR20","doi-asserted-by":"publisher","unstructured":"Guo J, Wu W (2021) A K-Hop Collaborate Game Model: Extended to Community Budgets and Adaptive Nonsubmodularity. IEEE Transactions on Systems, Man, and Cybernetics: Systems. https:\/\/doi.org\/10.1109\/TSMC.2021.3129276","DOI":"10.1109\/TSMC.2021.3129276"},{"key":"875_CR21","doi-asserted-by":"publisher","unstructured":"Guo J, Zhang Y, Wu W (2021) An Overall Evaluation on Benefits of Competitive Influence Diffusion. IEEE Transactions on Big Data. https:\/\/doi.org\/10.1109\/TBDATA.2021.3084468","DOI":"10.1109\/TBDATA.2021.3084468"},{"key":"875_CR22","doi-asserted-by":"crossref","unstructured":"Gupta A, Ligett K, McSherry G, Roth A, Talwar K (2010) Differentially private combinatorial optimization. In Proceedings of the 21st Annual ACM Symposium on Discrete Algorithms, p 1106-1125","DOI":"10.1137\/1.9781611973075.90"},{"key":"875_CR23","doi-asserted-by":"crossref","unstructured":"Gupta A, Roth A, Schoenebeck G, Talwar K (2010) Constrained non-monotone submodular maximization: Offline and secretary algorithms. The 6th International Workshop on Internet and Network Economics, p 246-257","DOI":"10.1007\/978-3-642-17572-5_20"},{"issue":"4","key":"875_CR24","doi-asserted-by":"publisher","first-page":"105","DOI":"10.4086\/toc.2015.v011a004","volume":"11","author":"D Kempe","year":"2015","unstructured":"Kempe D, Kleinberg J, Tardos \u00c9 (2015) Maximizing the Spread of Influence through a Social Network. Theory Comput 11(4):105\u2013147","journal-title":"Theory Comput"},{"issue":"2","key":"875_CR25","first-page":"235","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause A, Singh A, Guestrin C (2008) Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies. Journal of Machine Learning Research 9(2):235\u2013284","journal-title":"Journal of Machine Learning Research"},{"key":"875_CR26","doi-asserted-by":"crossref","unstructured":"Lee J, Mirrokni VS, Nagarajan V, Sviridenko M (2009) Non-monotone submodular maximization under matroid and knapsack constraints. In Proceedings of the 41th Annual ACM Symposium on Theory of Computing, p 323-332","DOI":"10.1145\/1536414.1536459"},{"key":"875_CR27","doi-asserted-by":"crossref","unstructured":"McSherry G, Talwar K (2007) Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 94-103","DOI":"10.1109\/FOCS.2007.66"},{"key":"875_CR28","unstructured":"Mirzasoleiman B, Badanidiyuru A, Karbasi A (2016) Fast constrained submodular maximization: Personalized data summarization. In Proceedings of the 33rd International Conference on Machine Learning, p 1358-1367"},{"key":"875_CR29","unstructured":"Mitrovic M, Bun, M, Krause A, Karbasi A (2017) Differentially private submodular maximization: Data summarization in disguise. In Proceedings of the 34th International Conference on Machine Learning, p 2478-2487"},{"issue":"3","key":"875_CR30","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA (1978) Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research 3(3):177\u2013188","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"875_CR31","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions-I. Math Progr 14(1):265\u2013294","journal-title":"Math Progr"},{"key":"875_CR32","doi-asserted-by":"crossref","unstructured":"Papadimitriou CH, Schapira M, Singer Y (2008) On the hardness of being truthful. In Proceedings of the 49th Annual Symposium on Foundations of Computer Science, p 250-259","DOI":"10.1109\/FOCS.2008.54"},{"key":"875_CR33","unstructured":"Rafiey A, Yoshida Y (2020) Fast and private submodular and $$k$$-submodular functions maximization with matroid constraints. In Proceedings of the 37th International Conference on Machine Learning, p 7887-7897"},{"key":"875_CR34","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k J (2008) Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, p 67-74","DOI":"10.1145\/1374376.1374389"},{"key":"875_CR35","doi-asserted-by":"crossref","unstructured":"Yoshida Y (2019) Cheeger inequalities for submodular transformations. In Proceedings of the 30th Annual ACM Symposium on Discrete Algorithms, p 2582-2601","DOI":"10.1137\/1.9781611975482.160"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00875-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00875-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00875-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T09:38:23Z","timestamp":1667036303000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00875-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,23]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["875"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00875-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,6,23]]},"assertion":[{"value":"11 June 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 June 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}