Robust Maximization of Correlated Submodular Functions

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 paper, 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 a modified greedy algorithm that exploits the correlation ratio to achieve a provable optimality bound. 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.