Abstract
In this paper, we present a thorough study of the regularized submodular maximization problem, in which the objective can be expressed as the difference between a submodular function and a modular function. This problem has drawn much attention in recent years. While existing works focuses on the case of g being monotone, we investigate the problem with a nonmonotone g. The main technique we use is to introduce a distorted objective function, which varies weights of the submodular component g and the modular component ℓ during the iterations of the algorithm. By combining the weighting technique and measured continuous greedy algorithm, we present an algorithm for the matroid-constrained problem, which has a provable approximation guarantee. In the cardinality-constrained case, we utilize random greedy algorithm and sampling technique together with the weighting technique to design two efficient algorithms. Moreover, we consider the unconstrained problem and propose a much simpler and faster algorithm compared with the algorithms for solving the problem with a cardinality constraint.
Acknowledgments
We are indebted to the associate editor and an anonymous reviewer for their valuable comments and suggestions, which help us improve the quality of this paper.
Disclosure statement
No potential conflict of interest was reported by the author(s).
Notes
1 See Section 2 for more details.
2 Namely, the algorithm returns a solution such that , where α is a constant in .
3 In Tables and , represents an optimal solution to the corresponding optimization problem.
4 See line 5 of Algorithm 1.
5 Throughout this paper, denotes set .
6 Every set A obeying the cardinality constraint is an independent set of a uniform matroid.
7 If and , then it holds that .