Robust Maximization of Correlated Submodular Functions under Cardinality and Matroid Constraints

Submodular maximization has applications in networked control, data summarization, and path planning, among other areas. While several efficient algorithms with provable optimality bounds have been developed for maximizing a single submodular function, the more computationally challenging problem of maximizing the minimum of a set of submodular functions (robust submodular maximization) has received less research attention. In this article, we investigate robust submodular maximization when the objective functions are correlated, i.e., the marginal benefits of adding elements to each function are within a given ratio of each other. We propose two modified greedy algorithms that exploit our defined correlation ratio to achieve the provable optimality bounds under matroid and cardinality constraints. As a case study, we consider minimization of graph effective resistance, and derive bounds on the correlation ratio using the graph spectrum. Our results are evaluated through numerical study.