  We examine the \emph{submodular maximum coverage problem} (SMCP), which is
related to a wide range of applications. We provide the first variational
approximation for this problem based on the Nemhauser divergence, and show that
it can be solved efficiently using variational optimization. The algorithm
alternates between two steps: (1) an E step that estimates a variational
parameter to maximize a parameterized \emph{modular} lower bound; and (2) an M
step that updates the solution by solving the local approximate problem. We
provide theoretical analysis on the performance of the proposed approach and
its curvature-dependent approximate factor, and empirically evaluate it on a
number of public data sets and several application tasks.
