Robust Maximization of Correlated Submodular Functions Under Cardinality and Matroid Constraints

• 成果类型: Article
• 署名作者: Hou, Qiqiang; Clark, Andrew
• 署名单位: Worcester Polytechnic Institute
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3061656
• 发表日期: 2021
• 页码: 6148-6155
• 关键词: Optimized production technology; correlation; resistance; optimization; minimization; Robustness; PLANNING; Combinatorial Optimization; effective resistance; robust optimization; Submodularity

摘要

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.