Title: Minimization Problems with Non-Submodular Cover Constraint
Abstract: The set cover problem has been studied extensively for many years. Submodular function plays a key role in combinatorial optimization. Extending the set cover problem, we consider three submodular cover problems. The first two problems minimize linear and submodular functions, respectively, subject to the same non-submodular cover constraint. The third problem minimizes a submodular function subject to non-submodular cover and precedence constraints. Based on the concepts of submodular ratio and gap, and Lovász extension, we devise greedy and primal–dual approximation algorithms for these problems.
Publication Year: 2023
Publication Date: 2023-03-23
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot