101. Minimization Problems with Non-Submodular Cover Constraint.
- Author
-
Wang, Wenqi, Liu, Zhicheng, Du, Donglei, Shi, Peihao, and Zhang, Xiaoyan
- Subjects
SUBMODULAR functions ,APPROXIMATION algorithms ,COMBINATORIAL optimization ,GREEDY algorithms - 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. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF