Keywords

1 Introduction

Submodular optimization is widely studied in optimization, computer science, and economics, etc. Submodularity is a very powerful tool in many optimization applications such as viral marketing [9, 18], recommendation system [12, 15, 21], nonparametric learning [1, 16], and document summarization [20], etc.

The greedy algorithm introduced by Nemhauser et al. [22] gave the first \((1-e^{-1})\)-approximation for monotone submodular maximization with a cardinality constraint (SMC). Feige [13] considered a maximal k-cover problem, which is a special case of SMC, and showed that there is no algorithms with approximation ratio greater than \((1-e^{-1}+\epsilon )\) for any \(\epsilon >0\), under the assumption P \(\ne \) NP. Sviridenko [23] considered a monotone submodular maximization with a knapsack constraint, and provided a tight \((1-e^{-1})\)-approximation algorithm with time complexity \(O(n^5)\). Calinescu et al. [8] provided a \((1-e^{-1})\)-approximation algorithm for monotone submodular maximization with a matroid constraint. All extant results of constrained submodular maximization assume monotonicity of the objective functions. In this paper, we consider a non-monotonic and non–submodular maximization problem subject to a more general p-independence system constraint.

1.1 Our Contributions

In this work, we consider a non-submodular maximization with an independence system constraint. Specifically, all feasible solutions associated with this model generate a p-independence system and the objective function is characterized by a series of parameters, such as submodularity (supmodularity) ratio, generalized curvature, and zero order approximate submodularity coefficient, etc. Our main results can be summarized as follows.

  • We first investigate the efficiency of a greedy algorithm with two scenarios. Firstly, the objective function is non-submodularity and non-monotonic. Secondly, the feasible solution belongs to a p-independence system. We show that some good properties are still retained in the non-submodular setting (Theorem 1).

  • Second we study the non-monotone non-submodular maximization problem without any constraint. Based on a simple approximate local search, for any \(\epsilon >0\) we show that there exists a polynomial time \((3/c^2+\epsilon )\)-approximation algorithm, where c is the zero order approximate submodularity coefficient of objective function (Theorem 2).

  • Finally, we apply the first two algorithms as the subroutines to solve a non-monotone non-submodular maximization problem with p-independence system constraint. Our algorithm is an extension of the Repeat-Greedy introduced in [15]. Based on a multiple times rounding of the above subroutine algorithms, we derived a nearly constant approximation ratio algorithm (Theorem 3).

1.2 The Organization

We give a brief summary of related work in Sect. 2. The necessary preliminaries and definitions are presented in Sect. 3. The main algorithms and analyses are provided in Sect. 4. We present a greedy algorithm in Sect. 4.1, an approximate local search in Sect. 4.2, and the core algorithm is provided in Sect. 4.3. In Sect. 5, we offer a conclusion for our work.

2 Related Works

Non-monotone Submodular Optimization. Unlike the monotone submodular optimization, there exists a natural obstacle in the study of non-monotonic case. For example, direct application of the greedy algorithm introduced by Nemhauser et al. [22] to the non-monotonic case does not yield a constant approximation guarantee. Some previous work is summarized below. For the non-monotone submodular maximization problem without any constraint (USM), Feige et al. [14] presented a series of algorithms. They first showed a uniform random algorithm has a \(1/4\)-approximation ratio. Second, they gave a deterministic local search \(1/3\)-approximation algorithm and a random \(2/5\)-approximation algorithm. For symmetric submodular functions, they derived a \(1/2\)-approximation algorithm and showed that any \((1/2+\epsilon )\)-approximation for symmetric submodular functions must need an exponential number of queries for any fixed \(\epsilon >0\). Based on local search technique, Buchbinder et al. [7] provided a random linear time \(1/2\)-approximation algorithm.

Optimization of non-monotone submodular with complex constraints are also considered previously. Buchbinder and Feldman [5] gave a deterministic \(1/2\)-approximation algorithm for USM with time complexity \(O(n^2)\). For non-monotone submodular maximization with cardinality constraint, they derived a deterministic \(1/e\)-approximation algorithm, which has a slightly better approximation ration than the random \((1/e+0.004)\)-approximation ratio by [6]. Buchbinder and Feldman [4] considered a more general non-monotone submodular maximization problem with matroid constraint and presented the currently best random 0.385-approximation algorithm. Lee et al. [19] derived a \(1/(p+1+1/(p-1)+\epsilon )\)-approximation algorithm as well as non-monotone submodular maximization algorithm with a constraint of the intersection of p matroids. For a more general p-independence system constraint, Gupta et al. [17] derived a \(1/3p\)-approximation, which needs \(O(np\ell )\) function value oracles, where \(\ell \) is the maximum size of feasible solutions. Mirzasoleiman et al. [21] improved the approximation ratio to \(1/2k\), while the time complexity was still bounded by \(O(np\ell )\). Recently, with improved time complexity of \(O(n\ell \sqrt{p})\), the approximation ratio was improved to \(1/(p+\sqrt{p})\) by Feldman et al. [15].

Non-submodular Maximization. There are also many problems in optimization and machine learning whose utility functions do not possess submodularity. Das and Kempe [11] introduced a definition of submodularity ratio \(\gamma \) to measure the magnitude of submodularity of the utility function. For the maximization of monotone non-submodular function with cardinality constraint (NSMC), they showed the greedy algorithm can achieve a \((1-e^{-\gamma })\)-approximation ratio. Conforti and Cornuéjols [10] studied the efficiency of the greedy algorithm by defining curvature \(\kappa \) of submodular objective functions for SMC and showed the approximation could be improved it to \(1/\kappa (1-e^{-\kappa })\). Bian et al. [2] introduced a more expressive formulation by providing a definition of the generalized curvature \(\alpha \) of any non-negative set function. Combining the submodularity ratio with the generalized curvature, they derived the tight \(1/\alpha (1-e^{1/(\alpha \gamma )})\)-approximation ratio of the greedy algorithm for NSMC. Inspired by these work, Bogunovic et al. [3] introduced further parameters, such as supmodularity ratio, inverse generalized curvature, etc., to characterize the utility function. They derived the first constant approximation algorithm for monotone robust non-submodular maximization problem with cardinality constraint.

3 Preliminaries

In this section, we present some necessary notations. We are given a ground set \({\mathcal {V}}=\{u_1,...,u_n\}\), and a utility function \(f:2^{{\mathcal {V}}}\rightarrow R_+\). The function f may not be submodular; namely the following zero order condition of submodular may not hold

$$\begin{aligned} f(A)+f(B)\ge f(A\cup B)+f(A\cap B), \forall A, B\subseteq {\mathcal {V}}. \end{aligned}$$

For our purpose, we define a parameter c to approximate the submodularity of our utility function.

Definition 1

Given an integer k, let \(\{A_i\}^{k}_{i=1}\) be a collection of subsets of \({\mathcal {V}}\). The zero order approximate submodularity coefficient is the largest \(c_k\in [0,1]\) such that

$$\begin{aligned} \sum \limits ^{k}_{i=1}f(A_i)\ge c_k\cdot [f(\cup _{i}A_i)+f(\cap _{i}A_i)]. \end{aligned}$$

For any \(A, B\subseteq {\mathcal {V}}\), we set \(f_{A}(B)=f(A\cup \{B\})-f(A)\) as the amount of change by adding B to A. For the sake of brevity and readability, we set \(f_{A}(u)=f(A+u)-f(A)\) for any singleton element \(u\in {\mathcal {V}}\). Then we restate the submodularity ratio \(\gamma \) in the following definition. The submodularity ratio measures how close of f being submodular.

Definition 2

([2, 3, 11]). Given an integer k, the submodularity ratio of a non-negative set function f with respect to \({\mathcal {V}}\) is

$$\begin{aligned} \gamma _{{\mathcal {V}},k}(f)=\min _{A\subseteq {\mathcal {V}}, B: |B|\le k, A\cap B=\emptyset }\frac{\sum _{u\in B}f_{A}(u)}{f_{A}(B)}. \end{aligned}$$

Let k be the maximum size of any feasible solution, and omit signs \(k, {\mathcal {V}}\) and f for clarity. Bian et al. [2] introduced an equivalent formulation of submodularity ratio \(\gamma \) by the largest \(\gamma \) such that

$$\begin{aligned} \sum \limits _{u\in B}f_{A}(u)\ge \gamma \cdot f_{A}(B), \forall A, B\subseteq {\mathcal {V}}, A\cap B=\emptyset . \end{aligned}$$

Bogunovic et al. [3] defined supmodularity ratio \({\check{\gamma }}\) that measures how close a utility function is supermodular.

Definition 3

([3]). The supmodularity ratio of a non-negative set function f is the largest \({\check{\gamma }}\) such that

$$\begin{aligned} f_{A}(B)\ge {\check{\gamma }}\cdot \sum \limits _{u\in B}f_{A}(u), \forall A, B\subseteq {\mathcal {V}}, A\cap B=\emptyset . \end{aligned}$$

For a monotone submodular function, Conforti and Cornuéjols [10] introduced the definition of total curvature \(\kappa _f\) and curvature \(\kappa _f(S)\) w.r.t. a set \(S\subseteq {\mathcal {V}}\) as follows. Denote \(\kappa _f=1-\min _{u\in {\mathcal {V}}}f_{{\mathcal {V}}\setminus \{u\}}(u)/f(u)\), and \(\kappa _f(S)=1-\min _{u\in S}f_{S\setminus \{u\}}(u)/f(u)\). Sviridenko et al. [24] provided a definition of curvature from submodular to non-submodular functions. The expanded curvature is defined as \(\kappa ^o=1-\min _{u\in {\mathcal {V}}}\min _{A, B\subseteq {\mathcal {V}}\setminus \{u\}}f_{A}(u)/f_{B}(u)\). Bian et al. [2] presented a more expressive formulation of curvature, which measures how close a set function is to being supmodular.

Definition 4

([2]). The generalized curvature of a non-negative function f is the smallest scalar \(\alpha \) such that

$$\begin{aligned} f_{A\setminus \{u\}\cup B}(u)\ge (1-\alpha )\cdot f_{A\setminus \{u\}}(u), \forall A, B\subseteq {\mathcal {V}}, u\in A\setminus B. \end{aligned}$$

Recently, Bogunovic et al. [3] introduced the concept of inverse generalized curvature \({\check{\alpha }}\), which can be described as follows:

Definition 5

([3]). The inverse generalized curvature of a non-negative function f is the smallest scalar \({\check{\alpha }}\) such that

$$\begin{aligned} f_{A\setminus \{u\}}(u)\ge (1-{\check{\alpha }})f_{A\setminus \{u\}\cup B}(u), \forall A, B\subseteq {\mathcal {V}}, u\in A\setminus B. \end{aligned}$$

The above parameters are used to characterize a non-negative set function from different points of view. We provide a lower bound of zero order approximate submodularity coefficient c by inverse generalized curvature \({\check{\alpha }}\). I.e., \(c\ge 1-{\check{\alpha }}\). The proof is referred to the full version. We omit the relation of the other parameters as they can be found in [2, 3]. In the rest of this part, we restate the concept of the p-independence system.

Let \({\mathcal {I}}=\{A_i\}_{i}\) be a finite collection of subsets chosen from \({\mathcal {V}}\). We say the tuple \(({\mathcal {V}}, {\mathcal {I}})\) is an independence system if for any \(A\in {\mathcal {I}}\), \(A^\prime \subseteq A\) implies that \(A^\prime \in {\mathcal {I}}\). The sets of \({\mathcal {I}}\) are called the independent sets of the independence system. An independent set B contained in a subset \(X\subseteq {\mathcal {V}}\) is a base (basis) of X if no other independent set \(A\subseteq X\) strictly contains B. By the above terminologies we restate the definition of p-independence system as follows.

Definition 6

([15]). An independence system \(({\mathcal {V}}, {\mathcal {I}})\) is a p-independence system if, for every subset \(X\subseteq {\mathcal {V}}\) and for any two bases \(B_1, B_2\) of X, we have \(|B_1|/|B_2|\le p\).

In our model, assume the utility function is characterized by these parameters, and the collection of all feasible subsets constructs a p-independence system. We also assume that there exist a utility function value oracle and an independence oracle; i.e., for any \(A\subseteq {\mathcal {V}}\), we can obtain the value of f(A) and know if A in \({\mathcal {I}}\) or not. The model can be described as follows:

$$\begin{aligned} \begin{aligned} OPT\leftarrow \arg \max _{S\subseteq {\mathcal {V}}, S\in {\mathcal {I}}}f(S), \end{aligned} \end{aligned}$$
(1)

where \(({\mathcal {V}},{\mathcal {I}})\) is a p-independence system.

4 Algorithms

In this section, we present some algorithms in dealing with non-submodular maximization. Before providing our main algorithm, we first investigate the efficiency of two sub-algorithms. In Subsect. 4.1, we restate the greedy algorithm for submodular maximization with p-independence system constraint, and show that some good properties are still retained in the non-submodular setting. In Subsect. 4.2, we present a local search for non-monotone non-submodular maximization without any constraint. Finally, we provide the core algorithm in Subsect. 4.3.

4.1 Greedy Algorithm Applied to Non-submodular Optimization

The pseudo codes of the greedy algorithm are presented in Algorithm 1. Let \(S^G=\{u_1,...,u_\ell \}\) be the returned set by Algorithm 1. We start with \(S^G=\emptyset \). In each iteration, we choose the element u with maximum gain, and add it to the current solution if it satisfies \(S^G+u\in {\mathcal {I}}\). For clarity, we let OPT be any optimum solution set of maximizing the utility function under p-independence system constraint. Then we can derive a lower bound of \(f(S^G)\) by the following theorem.

Theorem 1

Let \(S^G\) be the returned set of Algorithm 1, then we have

$$\begin{aligned} f(OPT\cup S^G)\le \left( \frac{p}{\gamma ^2{\check{\gamma }}(1-{\check{\alpha }})}+1\right) f(S^G). \end{aligned}$$

Proof

Refer to the full version of this paper.

figure a
figure b

Let \(B\in {\mathcal {I}}\) be any independent set and set \(S^G_{i}=\{u_1,...,u_i\}\) be the set of the first i elements added by Algorithm 1. We can iteratively construct a partition of B according to \(S^G\). We start with \(B_0=B\) and set \(B_i=\{u\in B\setminus S^G_i|S^G_i+u\in {\mathcal {I}}\}\) for iteration \(i\in [\ell ]=\{1,...,\ell \}\), where \(\ell \) denotes the size of \(S^G\) in the end. Then the collection of \(\{B_{i-1}\setminus B_i\}^\ell _{i=1}\) derives a partition of B. Let \(C_i=B_{i-1}\setminus B_i\) for any \(i\in [\ell ]\). The construction can be summarized as Algorithm 2. The properties of the above partition are presented in the following lemma.

Lemma 1

Let \(\{C_i\}^\ell _{i=1}\) be the returned partition of Algorithm 2, then

  • for each \(i\in [\ell ]\), we have \(\sum ^i_{j=1}p_j\le p\cdot i\) where \(p_j=|C_j|\); and

  • for each \(i\in [\ell ]\), we have \(p_i\cdot \delta _i\ge \gamma (1-{\check{\alpha }})f_{S^G}(C_i)\).

Proof

Refer to the full version of this paper.

4.2 Local Search Applied to Non-submodular Optimization

In this subsection, we present a local search algorithm for the non-monotone non-submodular maximization problem without any constraint. The main pseudo codes are provided by Algorithm 3. Feige et al. [14] introduced the local search approach to deal with the non-monotone submodular optimization problem. We extend their algorithm to the non-submodular setting, and show that the algorithm still keeps a near constant approximation ratio by increasing a factor.

In order to implement our algorithm in polynomial time, we relax the local search approach and find an approximate local solution. Let \(S^{LS}\) be the returned set of Algorithm 3 and let \(OPT^o\) be any optimum solution without any constraint. We restate the definition of approximate local optimum as follows.

Definition 7

([14]). Given a set function \(f:2^{{\mathcal {V}}}\rightarrow R\), a set \(A\subseteq {\mathcal {V}}\) is called a \((1+\lambda )\)-approximate local optimum if, \(f(A-u)\le (1+\lambda )\cdot f(A)\) for any \(u\in A\) and \(f(A+u)\le (1+\lambda )\cdot f(A)\) for any \(u\notin A\).

By the definition of the approximate local optimum solution, we show that there exists a similar performance guarantee in the non-submodular case. The details are summarized in the following theorem.

figure c

Theorem 2

Given \(\epsilon >0, c\) and \({\check{\alpha }}\in [0,1)\). Let \(S^{LS}\) be the returned set of Algorithm 3 by setting set \(\lambda = \frac{c^2\epsilon }{(1-{\check{\alpha }})n}\). We have

$$\begin{aligned} f(OPT^{o})\le \left( \frac{3}{c^2}+\epsilon \right) \cdot f(S^{LS}). \end{aligned}$$

Proof

Refer to the full version of this paper.

Before proving the above theorem, we need the following lemma.

Lemma 2

If S is a \((1+\lambda )\)-approximate local optimum for a non-submodular function f, then for any set T such that \(T\subseteq S\) or \(T\supseteq S\), we have

$$\begin{aligned} f(T)\le [1+\lambda n(1-{\check{\alpha }})]\cdot f(S). \end{aligned}$$

Proof

Let \(S=\{u_1,...,u_q\}\) be a \((1+\lambda )\)-approximate local optimum solution returned by Algorithm 3. W.l.o.g., we assume \(T\subseteq S\), then we construct \(T_i\) such that \(T=T_1\subseteq T_2\subseteq \cdots \subseteq T_r=S\) and \(u_i=T_i\setminus T_{i-1}\). For each \(i\in \{2,...,q\}\), we have

$$\begin{aligned} \begin{aligned} f(T_i)-f(T_{i-1})\ge (1-{\check{\alpha }})(f(S)-f(S-u_i))\ge -\lambda (1-{\check{\alpha }})f(S),\\ \end{aligned} \end{aligned}$$

where the first inequality follows by the definition of the inverse generalized curvature and the second inequality follows by the definition of the approximate local optimum. Summing up the above inequalities, we have

$$\begin{aligned} \begin{aligned} f(S)-f(T)=\sum \limits ^{q}_{i=2}\left[ f(T_i)-f(T_{i-1})\right] \ge -\lambda q(1-{\check{\alpha }})f(S), \end{aligned} \end{aligned}$$

implying that \(f(T)\le [1+\lambda q(1-{\check{\alpha }})]f(S)\le [1+\lambda n(1-{\check{\alpha }})]f(S)\), where the second inequality follows from \(q\le n\). Simultaneously, the case of \(T\supseteq S\) can be similarly derived by the above process.

4.3 The Core Algorithm

In this subsection, we present the main algorithm, which is an extension of the Repeat-Greedy algorithm introduced in [15]. The pseudo codes are presented as Algorithm 4. We run the main algorithm in r rounds. Let \({\mathcal {V}}_i\) be the set of candidate elements set at the start of round \(i\in [r]\). We first run the greedy step of Algorithm 1. Then, we proceed with the local search step of Algorithm 3 on the set returned from the first step. Simultaneously, we update the candidate ground set as \({\mathcal {V}}_i={\mathcal {V}}\setminus {\mathcal {V}}_{i-1}\). Finally, we output the best solution among all returned sets. We can directly obtain two estimations of the utility function by Theorems 1 and 2, respectively. The results are summarized as follows.

Lemma 3

For any iteration \(i\in [r]\) of Algorithm 4, we have

  1. 1.

    \(f(S_i\cup (OPT\cap {\mathcal {V}}_i))\le \left( \frac{p}{\gamma ^2{\check{\gamma }}(1-{\check{\alpha }})}+1\right) f(S_i)\), and

  2. 2.

    \(f(S_i\cap OPT )\le \left( \frac{3}{c^2}+\epsilon \right) f(S^\prime _i)\).

Buchbinder et al. [6] derived an interesting property in dealing with non-monotone submodular optimization problems. Now, we extend this property to the non-submodular case, as summarized in the following lemma.

Lemma 4

Let \(g: 2^{\mathcal {V}} \rightarrow R_+\) be a set function with inverse generalized curvature \({\check{\alpha }}_g\), and S be a random subset of \({\mathcal {V}}\) where each element appears with probability at most \(\mathrm {pr}\) (not necessarily independent). Then \({\mathbf {E}}[g(S)]\ge \left[ 1-(1-{\check{\alpha }}_g)\mathrm {pr}\right] \cdot g(\emptyset )\).

Proof

Refer to the full version of this paper.

Using this result, we can derive an estimation of f(OPT). Let S be a random set of \(\{S_i\}^r_{i=1}\) with probability \(\mathrm {pr}=\frac{1}{r}\) and set \(g(S)=f(OPT\cup S)\) for any \(S\subseteq {\mathcal {V}}\). Then we have \({\check{\alpha }}={\check{\alpha }}_f={\check{\alpha }}_g\). By Lemma 4, we yield

$$\begin{aligned} \begin{aligned} \frac{1}{r}\sum \limits ^{r}_{i=1}f(S_i\cup OPT)={\mathbf {E}}[f(S\cup OPT)]&={\mathbf {E}}[g(S)]\ge [1-(1-{\check{\alpha }}_g)\mathrm {pr}]\cdot g(\emptyset )\\&=\left( 1-\frac{1-{\check{\alpha }}}{r}\right) \cdot f(OPT). \end{aligned} \end{aligned}$$

Multiplying both sides of the last inequality by r, we get

$$\begin{aligned} \begin{aligned} \sum \limits ^{r}_{i=1}f(S_i\cup OPT)\ge [r-(1-{\check{\alpha }})]\cdot f(OPT). \end{aligned} \end{aligned}$$
(2)

The following lemma presents a property based on zero order approximate submodularity coefficient of the objective function.

Lemma 5

([15]). For any subsets \(A, B, C\subseteq {\mathcal {V}}\), we have

$$\begin{aligned} \begin{aligned} f(A\cup B)\le \frac{1}{c}\cdot [f(A\cup (B\cap C))+f(B\setminus C)]. \end{aligned} \end{aligned}$$
figure d

Proof

To prove this lemma, we have the following

$$\begin{aligned} \begin{aligned} f(A\cup B)&=f(A\cup (B\cap C)\cup (B\setminus C))\\&\le f(A\cup (B\cap C)\cup (B\setminus C))+f(A\cup (B\cap C)\cap (B\setminus C))\\&\le \frac{1}{c}\cdot \left[ f(A\cup (B\cap C))+f(B\setminus C)\right] , \end{aligned} \end{aligned}$$

where the first inequality follows from the nonnegativity of the objective function and the second inequality is derived by the definition of the zero order approximate submodularity coefficient c.

From these lemmas and choosing properly the number of rounds, we conclude that if the parameters of the utility function are fixed, or have a food estimation, then Algorithm 4 yieds a near constant performance guarantee for problem (1). The details are presented in the following theorem.

Theorem 3

Give an objective function \(f:2^V\rightarrow R_+\) with parameters \(c, \gamma , {\check{\gamma }}, {\check{\alpha }}\), and a real number \(\epsilon >0\), let S be the returned set of Algorithm 4. Set \(r=\left\lceil \varDelta \right\rceil \). Then we have

$$\begin{aligned} \begin{aligned} \frac{f(OPT)}{ f(S)}\le \left[ \left( \frac{p}{\gamma ^2{\check{\gamma }}c (1-{\check{\alpha }})}+\frac{3\varDelta }{2c^4}+\frac{1}{c}\right) +\frac{\epsilon \varDelta }{2c^4}\right] \cdot \left[ 1-(1-{\check{\alpha }})\cdot (\varDelta +1)\right] ^{-1}, \end{aligned} \end{aligned}$$

where

$$\begin{aligned} \begin{aligned} \varDelta =(1-{\check{\alpha }})+\sqrt{(1-{\check{\alpha }})^2+(1-{ \check{\alpha }})\left( \frac{2c^3}{3+c^2\epsilon }+1\right) +\frac{p}{ \gamma ^2{\check{\gamma }}}\cdot \frac{2c^3}{3+c^2\epsilon }}. \end{aligned} \end{aligned}$$

Proof

Refer to the full version of this paper.

5 Conclusion

We consider the non-submodular and non-monotonic maximization problem with a p-independence system constraint, where the objective utility function is characterized by a set of parameters such as submodularity (supmodularity) ratio, inverse generalized curvature, and zero order approximate submodularity coefficient. We study a greedy algorithm applied to non-submodular optimization with p-independence system constraint, and show the algorithm preserves some good properties even though the objective function is non-submodularity. Then, we investigate the unconstrained non-submodular maximization problem. Utilizing an approximate local search technique, we derive an \(O(3/c^2+\epsilon )\)-approximation algorithm, where c is the zero order approximate submodularity coefficient. Finally, combining these two algorithms, we obtain an almost constant approximation algorithm for the non-monotone non-submodular maximization problem with p-independence system constraint.