Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration

Submodular function maximization is a critical building block for diverse tasks, such as document summarization, sensor placement, and image segmentation. Yet its practical utility is often limit by the $O(kn{d}^2)$ computational bottleneck. In this paper, we propose an integrated framework that addresses efficiency and privacy simultaneously. First, we introduce a novel matrix-based computation paradigm that accelerates function evaluations. Second, we develop approximate data structures that further streamline the optimization process, achieving a theoretical complexity of $O({\epsilon }^{-2}(nd+kn+k{d}^2)\log (k\mathrm{/}\delta ))$. Third, we integrate ($\epsilon ,\delta$)-DP guaranties to address the privacy concerns inherent in sensitive optimization tasks.