We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Maximizing a non-decreasing non-submodular function subject to various types of constraints.
- Authors
Lu, Cheng; Yang, Wenguo; Yang, Ruiqi; Gao, Suixiang
- Abstract
In this paper, we firstly study the problem of maximizing a γ -weakly DR-submodular function under a general matroid constraint. We present a local search algorithm, which is guided by a tailored potential function, for solving this problem. We prove that our algorithm produces a ( 1 - e - γ - ϵ )-approximate solution. To the best of our knowledge, it's the first algorithm achieving the tight approximation guarantee for such maximization problem. In addition, we study the maximization of the sum of submodular and supermodular functions. We show that this problem can be reduced to the maximization of submodular and linear sums. Based on this reduction, we derive new and improved approximation bounds for the problem under various types of constraints.
- Subjects
SUBMODULAR functions; SEARCH algorithms; PROBLEM solving; EXPECTATION-maximization algorithms
- Publication
Journal of Global Optimization, 2022, Vol 83, Issue 4, p727
- ISSN
0925-5001
- Publication type
Article
- DOI
10.1007/s10898-021-01123-x