@article{Chaturvedi_Nguyễn_Zakynthinou_2021, title={Differentially Private Decomposable Submodular Maximization}, volume={35}, url={https://ojs.aaai.org/index.php/AAAI/article/view/16860}, DOI={10.1609/aaai.v35i8.16860}, abstractNote={We study the problem of differentially private constrained maximization of decomposable submodular functions. A submodular function is decomposable if it takes the form of a sum of submodular functions. The special case of maximizing a monotone, decomposable submodular function under cardinality constraints is known as the Combinatorial Public Projects (CPP) problem (Papadimitriou, Schapira, and Singer 2008). Previous work by Gupta et al. (2010) gave a differentially private algorithm for the CPP problem. We extend this work by designing differentially private algorithms for both monotone and non-monotone decomposable submodular maximization under general matroid constraints, with competitive utility guarantees. We complement our theoretical bounds with experiments demonstrating improved empirical performance.}, number={8}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Chaturvedi, Anamay and Nguyễn, Huy Lê and Zakynthinou, Lydia}, year={2021}, month={May}, pages={6984-6992} }