Multi-Objective Submodular Maximization with Differential Privacy
It addresses the novel problem of privately optimizing multiple submodular objectives simultaneously, which is relevant for applications like privacy-preserving facility location.
This paper introduces the first study of multi-objective submodular maximization under differential privacy, proposing two DP algorithms that achieve approximation guarantees. Experiments on maximum coverage and facility location validate their efficacy.
In this paper, we study multi-objective submodular maximization (MOSM) subject to a cardinality constraint under differential privacy (DP). Specifically, we aim to select a set of at most $k \in \mathbb{Z}_{+}$ elements to maximize the minimum of $d > 1$ monotone submodular functions while satisfying $\varepsilon$-DP. Although extensive studies have been conducted on both differentially private single-objective submodular maximization on sensitive data and non-private MOSM, to the best of our knowledge, there has not yet been any prior work on MOSM with DP. We propose two novel algorithms: the first extends the classic greedy algorithm and the second employs a truncation technique, both of which are integrated with DP mechanisms for privacy protection and achieve approximation guarantees for MOSM. Finally, we conduct numerical experiments on two submodular maximization applications, namely maximum coverage and facility location, in multi-objective settings to validate the efficacy and efficiency of our proposed algorithms.