Variational Optimization for the Submodular Maximum Coverage Problem

06/10/2020
by   Jian Du, et al.
0

We examine the 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 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset