Regularized nonmonotone submodular maximization

Abstract

In this paper, we present a thorough study of the regularized submodular maximization problem, in which the objective $f:=g-\ell$ 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.

Keywords:

• Submodular maximization
• regularized problem
• continuous greedy algorithm
• random greedy algorithm
• sampling

AMS Classifications:

• 90C27
• 90C59
• 68Q25

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 $S\in \mathcal{F}$ such that $g(S)-\ell (S)\ge \alpha \cdot max\{g(A)-\ell (A):A\in \mathcal{F}\}$, where α is a constant in $(0,1]$.

3 In Tables 1 and 2, $S^{\star }$ represents an optimal solution to the corresponding optimization problem.

4 See line 5 of Algorithm 1.

5 Throughout this paper, $[k]$ denotes set $\{1,2,\dots ,k\}$.

6 Every set A obeying the cardinality constraint is an independent set of a uniform matroid.

7 If $a_1\ge a_2\ge \cdots \ge a_n$ and $b_1\ge b_2\ge \cdots \ge b_n$, then it holds that $\frac{1}{n}\sum _{k=1}^n{a}_k{b}_k\ge (\frac{1}{n}\sum _{k=1}^n{a}_k)\cdot (\frac{1}{n}\sum _{k=1}^n{b}_k)$.

Additional information

Funding

This research was supported by the National Natural Science Foundation of China [grant numbers 11991022 and 12071459] and the Fundamental Research Funds for the Central Universities [grant number E1E40107X2].