Search papers, labs, and topics across Lattice.
This paper addresses the challenge of multi-objective submodular maximization (MOSM) under differential privacy, aiming to select a set of elements that maximizes the minimum of multiple monotone submodular functions while adhering to privacy constraints. The authors introduce two innovative algorithms: one that extends the classic greedy approach and another utilizing a truncation technique, both designed to ensure privacy while achieving approximation guarantees. Experimental results on applications such as maximum coverage and facility location demonstrate the effectiveness and efficiency of these algorithms in a multi-objective context.
Achieving differential privacy in multi-objective submodular maximization opens new avenues for handling sensitive data without sacrificing performance.
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.
