k-Submodular Maximization with a Knapsack Constraint and p Matroid Constraints

Assume $f$ is a nonnegative, monotone, and $k$ -submodular function, the $k$ -submodular maximization problem over $E$ is to find an element $s\in {(k+1)}^E$ , such as to maximize $f(s)$ . That is,

(1) $$\max \{f(s)|s\in {(k+1)}^E\}$$

Algorithm 1 does not care about the order of items selected from $E$ , and each selected item is placed in the position with the largest marginal gain. From Ward and $\check{\mathrm{Z}}$ ivn $\acute{\mathrm{y}}$ ^{[ 14 ]}, Algorithm 1 provides a $1/2$ -approximate solution. We use $\tilde{s}$ to denote an outputs of Algorithm 1 and $OP{T}_f(E)$ to denote the optimal value. The corresponding result holds.

Lemma 3 ^{[ 14 ]} A $1/2$ -approximate solution $\tilde{s}$ of Formula (1) can be obtained, that is, $OP{T}_f(E)⩽2f(\tilde{s})$ .

In this section, we assume that a function $f$ is nonnegative monotone $k$ -submodular and $f(\mathrm{\varnothing })=0$ . Let $s^{*}\in {(k+1)}^E$ be an optimal solution of Formula (2). We will propose a deterministic algorithm (see Algorithm 2) for the maximization problem of $k$ -submodular function under a knapsack constraint and a matroid constraint. Firstly, we guess two items with the largest marginal gains in the optimal solution through enumeration as the initial solution $s^0$ . For every current solution s, we have the collection $L(s)$ of all $\text{swaps}(a,b)$ . Algorithm 2 picks each swap with the largest marginal profit density $\rho (a,b)$ in $L(s)\backslash \{\text{swap}(a,b)|b\in U(s^0)\}$ . The judgement statement $added=true\text{or}false$ controls to pass in and out of “while” loops. It changes as the current solution is updated.

When the picked swap passes conditions of Line 8, we update the support set of current solution s and rearrange the positions of these elements by Algorithm 1. Considering the order of each element in $(U(s\setminus s^0)\setminus \{b\})\cup \{a\}$ as it is added to s, we find the greedy position for every element with the same order. By Lemma 2, we input $f(s^{\prime }\bigsqcup s^0):{(k+1)}^{(U(s\setminus s^0)\setminus \{b\})\cup \{a\}}\to {\text{𝐑}}_{+}$ instead of $f(s^{\prime }):{(k+1)}^{(U(s\setminus s^0)\setminus \{b\})\cup \{a\}}\to {\text{𝐑}}_{+}$ . We update the current solution $s=s^{\prime }\bigsqcup s^0$ in the rearranged positions and its knapsack value $c_s$ . In order to regenerate $L(s)\backslash \{\text{swap}(a,b)|b\in U(s^0)\}$ , we change $added=true$ to $added=flase$ . Algorithm 2 break the loop in Lines 6–15 and regenerate $L$ in Line 5. To continue running the algorithm, we need to change $added=flase$ to $added=true$ . Until now, the process of updating the current solution is completed.

When the picked swap violates conditions of Line 8, Algorithm 2 removes the swap and picks next swap. In addition, nothing will be changed. It implies that $added=true$ always holds and the loop in Lines 6–15 continues running. Repeat the above process until Algorithm 2 finds a swap to update s or all swaps are removed. In the last iteration, all of swaps violate conditions of Line 8, then all of them are removed. Due to $L=\mathrm{\varnothing }$ in Line 6, Algorithm 2 break all loops and return the output solution.

A useful property of matroid is proposed by Sarpatwar et al.^{[ 6 ]} In order to understand it easily, we propose a new and detailed idea of proof as follows.

Lemma 5 ^{[ 6 ]} For any sets $A_1,A_2\in ℱ$ , we can always construct a mapping $b:A_2\backslash A_1\to (A_1\backslash A_2)\cup \{\mathrm{\varnothing }\}$ , where each element $u\in A_2\backslash A_1$ satisfies $(A_1\backslash \{b(u)\})\cup \{u\}\in ℱ$ , and $y\in A_1\backslash A_2$ satisfies $|b^{-1}(y)|⩽1$ .

Proof For convenience of explanation, we divide the given $A_1,A_2\in ℱ$ into several parts. We set $A:=A_1\cap A_2$ , $A_1=A\cup D$ and $A_2=A\cup B\cup C$ , where $B$ is the collection of all elements $u\in A_2\backslash A_1$ , such that $A_1\cup \{u\}\in ℱ$ , $C$ is the collection of all elements $u\in A_2\backslash A_1$ , such that $A_1\cup \{u\}\notin ℱ$ , and $D:=A_1\backslash A_2$ . We will construct a qualified mapping $b:B\cup C\to D\cup \{\mathrm{\varnothing }\}$ .

Firstly, when $u$ belongs to $B$ , we make $b(u)=\mathrm{\varnothing }$ . Next, let’s construct the other part of the corresponding relationships on $C$ and $D$ as follows.

Note that $|C|⩽|D|$ holds. In fact, we assume that $|C|>|D|$ , then there is $|A\cup C|>|A\cup D|$ . Using the definition of matroid, there exists an element $u\in (A\cup C)\backslash (A\cup D)\subseteq C$ , such that $A_1\cup \{u\}\in ℱ$ , which contradicts the definition of $C$ . So we always have $|C|⩽|D|$ .

Let $|D|=m⩾1$ . If $m=1$ , we take $D=\{y\}$ . Again $|C|⩽|D|⩽1$ , there is $C=\{u\}$ and $(A_1\backslash \{y\})\cup \{u\}=A\cup \{u\}\subseteq A_2\in ℱ$ .

We consider the case of $m>1$ . For a fixed $u\in C$ , there are $A\cup \{u\}\in ℱ$ and $|A\cup \{u\}|<|A_1|=|A\cup D|$ . According to the definition of matroid, there exists an element $y_1\in A_1\backslash (A\cup \{u\})=D$ , such that $A\cup \{u\}\cup \{y_1\}\in ℱ$ . Repeatedly using the definition of matroid, we can always find $y_i\in D$ , such that $A\cup \{u\}\cup \{y_1,\mathrm{\dots },y_i\}\in ℱ$ , for all $i\in [m-1]$ . Again $|D|=m$ , we set $D=\{y_1,\mathrm{\dots },y_{m-1},y\}$ and $b(u)=y$ . Then $A_1\setminus \{y\}\cup \{u\}=A\cup \{u\}\cup \{y_1,\mathrm{\dots },y_i\}\in ℱ$ holds.

We update the sets $\bar{C}=C\backslash \{u\}$ and $\bar{D}=D\backslash \{y\}$ . Similar to the above method, we can find a corresponding point in $\bar{D}$ for the next elment in $C$ . In this way, each element $u\in C$ corresponds to $b(u)\in D$ . Therefore, We construct a mapping $b$ : $u\to \mathrm{\varnothing }$ , for any $u\in B$ and $u\to b(u)$ , for any $u\in C$ with corresponding $b(u)\in D$ . It follows that $|b^{-1}(y)|⩽1$ holds, for any element $y\in A_1\setminus A_2$ .

■

Theorem 2 According to Algorithm 2, a ${\displaystyle \frac{1}{4}}(1-1/e^2)$ -approximate solution s of Formula (2) can be obtained.

Proof Since Lemma 5 and $U(s)\in ℱ$ , there exists a swap $(u,b(u))\in L$ for any $u\in U(s^{*})\setminus U(s)$ . In Line 8 of Algorithm 2, we need to check whether the swap is acceptable. Then the outputs s need to satisfy that for each $u\in U(s^{*})\setminus U(s)$ , the corresponding swap is rejected. In the following, we will discuss it in two cases.

Case 1: For all elements $u\in U(s^{*})\setminus U(s)$ , the swap $(u,b(u))$ satisfied $c_u-c_{b(u)}+c_s⩽c$ . Then the swap $(u,b(u))$ is rejected just because $\rho (u,b(u))⩽0$ . Then

(5) $$f(s^{*})-f(s)⩽$$ $$OP{T}_{f(s^{\prime }\bigsqcup s^0)}(U(s^{*}\setminus s^0)\cup U(s\setminus s^0))-f(s)⩽$$ $$2f(\tilde{s})-f(s)⩽$$ $$2{\displaystyle \underset{e_{ui}⪯\tilde{s}\setminus s}{\sum }}[f(s\bigsqcup e_{ui})-f(s)]+f(s)⩽$$ $${\displaystyle \underset{e_{\mathrm{ui}}⪯\tilde{s}\setminus s}{\sum }}2[f((s\setminus e_{b(u)j})\bigsqcup e_{ui})-f(s\setminus e_{b(u)j})]+f(s)⩽$$ $${\displaystyle \underset{e_{ui}⪯\tilde{s}\setminus s}{\sum }}2[f(s)-f(s\setminus e_{b(u)j})]+f(s)$$

Here $\tilde{s}=s^{\prime }\bigsqcup s^0$ , where $s^{\prime }$ is obtained by Algorithm 1 to maximize $h(s^{\prime })=f(s^{\prime }\bigsqcup s^0)$ over items $U(s^{*}\setminus s^0)\cup U(s\setminus s^0)$ . Firstly, we consider the order of each element in $U(s)$ as it is added to s in Algorithm 2. Then we add elements in $U(s^{*})\setminus U(s)$ in the same order and get $\tilde{s}$ . By Lemmas 2 and 3, we know that $OP{T}_{f(s^{\prime }\bigsqcup s^0)}(U(s^{*}\setminus s^0)\cup U(s\setminus s^0))⩽2f(\tilde{s})$ and $s⪯\tilde{s}$ . The third inequality in Formula (5) is obtained from Lemma 1. And the fourth follows from orthant submodularity. By our assumption about the swaps, the last inequality holds. Let $\{(b(u),$ $j)\}{}_{u\in \tilde{s}\setminus s}\setminus \mathrm{\varnothing }=\{(b_1,j_1),\mathrm{\dots },(b_K,j_K)\}$ , where we assign arbitrarily the indices $K⩽|\tilde{s}\setminus s|.$ Then, amplifying Formula (5) with $k$ -submodularity and monotonicity, we have

(6) $$f(s^{*})-2f(s)⩽$$ $${\displaystyle \underset{e_{ui}⪯\tilde{s}\setminus s}{\sum }}2[f(s)-f(s\setminus e_{b(u)j})]⩽$$ $${\displaystyle \underset{i=1}{\overset{K}{\sum }}}2{\mathrm{\Delta }}_{e_{b_i{j}_i}}f(e_{b_1{j}_1}\bigsqcup \mathrm{\cdots }\bigsqcup e_{b_{i-1}{j}_{i-1}})⩽$$ $$2f(e_{b_1{j}_1}\bigsqcup \mathrm{\cdots }\bigsqcup e_{b_K{j}_K})⩽2f(s)$$

Therefore, we get a $1/4$ -approximation to the optimum in this case.

$\mathrm{𝐂𝐚𝐬𝐞}\mathrm{𝟐}\mathbf{\text{:}}$ For the elements $u\in U(s^{*})\setminus U(s)$ , at least one swap $(u,b(u))$ violates the knapsack constraint, that is, $c_u-c_{b(u)}+c_s>c$ .

In Algorithm 2, the set generated in the $l$ -th iteration is recorded as $s^l$ . By Lemma 5, there exists a mapping $b_l:U(s^{*})\setminus U(s^l)\to (U(s^l)\setminus U(s^{*}))\cup \{\mathrm{\varnothing }\}$ , such that $(U(s^l)\setminus \{b_l(u)\})\cup \{u\}\in ℱ$ , for each $u\in U(s^{*})\setminus U(s^l)$ . Suppose that swap $(u^{*},b_{t^{*}}(u^{*}))$ is rejected for violating the knapsack constraint for the first time, where $u^{*}\in U(s^{*})\setminus U(s^{t^{*}})$ , $e_{u^{*}{j}_{u^{*}}}⪯s^{*}$ and $e_{b_{t^{*}}(u^{*})j_{t^{*}}}⪯s^{t^{*}}$ . By orthant submodularity and monotonicity, we have

(7) $$f((s^{t^{*}}\setminus e_{b_{t^{*}}(u^{*})j_{t^{*}}})\bigsqcup e_{u^{*}{j}_{u^{*}}})-f(s^{t^{*}})⩽$$ $$f((s^{t^{*}}\setminus e_{b_{t^{*}}(u^{*})j_{t^{*}}})\bigsqcup e_{u^{*}{j}_{u^{*}}})-f(s^{t^{*}}\setminus e_{b_{t^{*}}(u^{*})j_{t^{*}}})⩽$$ $$f(x_1\bigsqcup e_{u^{*}{j}_{u^{*}}})-f(x_1)⩽f(x_1\bigsqcup x_2)-f(x_1)⩽$$ $$f(x_1)$$

So the following inequality holds:

(8) $$f((s^{t^{*}}\setminus e_{b_{t^{*}}(u^{*})j_{t^{*}}})\bigsqcup e_{u^{*}{j}_{u^{*}}})-f(s^{t^{*}})⩽\frac{f(x_1\bigsqcup x_2)}{2}$$

We define a function $g(s):D(s^0)\to R$ as $g(s)=f(s)-f(s^0)$ , where $D(s^0):=\{s\in {(k+1)}^E|s^0⪯s\}.$ It is obviously that $g(s)$ is also $k$ -submodular and monotone. In the following we will prove that

$$g((s^{t^{*}}\setminus e_{b_{t^{*}}(u^{*})j_{t^{*}}})\bigsqcup e_{u^{*}{j}_{u^{*}}})⩾\frac{1}{4}(1-{\text{e}}^{-2})g(s^{*}).$$

Note that a swap $(u^t,b_t(u^t))$ occurs in each iteration of Algorithm 2 for $t\in \{0,1,\mathrm{\dots },t^{*}-1\}$ . For simplicity, we denote $\rho (u^t,b_t(u^t))$ by ${\rho }_t$ . We greedily add elements in $U(s^{*})\setminus U(s^t)$ to $s^t$ one by one, and construct a set $\hat{s}$ over $U=U(s^{*})\cup U(s^t)$ for $t\in \{0,1,\mathrm{\dots },t^{*}-1\}$ . Clearly $s^t⪯\hat{s}$ . Let $s^{\prime }\in {(k+1)}^{E\setminus U(s^0)}$ , by Lemma 3 and Lemma 1, we have

(9) $$g(s^{*})⩽OP{T}_{g(s^{\prime }\bigsqcup s^0)}(U(s^{*}\setminus s^0)\cup U(s^t\setminus s^0))⩽$$ $$2g(\hat{s})⩽$$ $$2g(s^t)+2{\displaystyle \underset{e_{ui}⪯\hat{s}\setminus s^t}{\sum }}(g(s^t\bigsqcup e_{ui})-g(s^t))$$

Since $g$ is $k$ -submodular, for each $e_{ui}⪯\hat{s}\setminus s^t$ , there is a swap $(u,b_t(u))$ satifying the inequalities in the following:

(10) $$g(s^t\bigsqcup e_{ui})-g(s^t)⩽$$ $$g((s^t\setminus e_{b_t(u)j})\bigsqcup e_{ui})-g(s^t\setminus e_{b_t(u)j})=$$ $$[g(s^t)-g(s^t\setminus e_{b_t(u)j})]+$$ $$[g((s^t\setminus e_{b_t(u)j})\bigsqcup e_{ui})-g(s^t)]$$

where $e_{b_t(u)j}⪯s^t$ . By the choice of ${\rho }_{t+1}$ and $c_{\hat{s}\setminus s^t}⩽c-c_{s^0}$ , we have

(11) $${\displaystyle \underset{e_{ui}⪯\hat{s}\setminus s^t}{\sum }}[g((s^t\setminus e_{b_t(u)j})\bigsqcup e_{ui})-g(s^t)]=$$ $${\displaystyle \underset{e_{ui}⪯\hat{s}\setminus s^t}{\sum }}[f((s^t\setminus e_{b_t(u)j})\bigsqcup e_{ui})-f(s^t)]⩽$$ $${\displaystyle \underset{e_{ui}⪯\hat{s}\setminus s^t}{\sum }}{c}_u{\rho }_{t+1}⩽(c-c_{s^0}){\rho }_{t+1}$$

We define ${\{(b_t(u),j)\}}_{u\in U(\hat{s}\setminus s^t),b_t(u)\in U(s^t)\setminus U(s^{*})}=\{(b_1,j_1),\mathrm{\dots },(b_K,j_K)\}$ , where $K⩽|\hat{s}\setminus s^t|$ . Similar to Formula (6), we have

(12) $${\displaystyle \underset{e_{ui}⪯\hat{s}\setminus s^t}{\sum }}[g(s^t)-g(s^t\setminus e_{b_t(u)j})]⩽$$ $${\displaystyle \underset{i=1}{\overset{K}{\sum }}}{\mathrm{\Delta }}_{e_{b_i{j}_i}}g(s^0\bigsqcup e_{b_1{j}_1}\mathrm{\cdots }\bigsqcup e_{b_{i-1}{j}_{i-1}})⩽g(s^t)$$

Thus, Formulas (9)–(12) imply that

(13) $$g(s^{*})⩽4g(s^t)+2(c-c_{s^0}){\rho }_{t+1}$$

for all $t\in \{1,\mathrm{\dots },t^{*}\}$ . Let $c_0=0$ and $c_t={\sum }_{\tau =1}^t{c}_{u^{\tau }}$ , for any $t\in \{1,\mathrm{\dots },t^{*}+1\}$ . Define $c^{\prime }=c_{t^{*}+1}$ and $c^{\mathrm{\prime \prime }}=c-c_{s^0}$ . By the assumption of Case 2, we have $c^{\prime }>c⩾c^{\mathrm{\prime \prime }}$ . For $j=1,\mathrm{\dots },c^{\prime }$ , we define ${\gamma }_j={\rho }_t$ when $j=c_{t-1}+1,\mathrm{\dots },c_t$ . Note that $c_{u^{\tau }}=(g(s^{\tau })-g(s^{\tau -1}))/{\rho }_{\tau }$ , using the above definition, we obtain that

(14) $$g(s^t)=\underset{\tau =1}{\overset{t}{\sum }}[g(s^{\tau })-g(s^{\tau -1})]=\underset{\tau =1}{\overset{t}{\sum }}{c}_{u^{\tau }}{\rho }_{\tau }=\underset{j=1}{\overset{c_t}{\sum }}{\gamma }_j$$

for $t\in \{1,\mathrm{\dots },t^{*}\}$ , and

(15) $$g((s^{t^{*}}\setminus e_{b_{t^{*}}(u^{*})j_{t^{*}}})\bigsqcup e_{u^{*}{j}_{u^{*}}})=$$ $${\displaystyle \underset{t=1}{\overset{t^{*}+1}{\sum }}}[g(s^t)-g(s^{t-1})]=$$ $${\displaystyle \underset{t=1}{\overset{t^{*}+1}{\sum }}}{c}_{u^t}{\rho }_t={\displaystyle \underset{j=1}{\overset{c^{\prime }}{\sum }}}{\gamma }_j$$

Using Formulas (13) and (14), we have

(16) $$g(s^{*})⩽\underset{t\in \{1,\mathrm{\dots },t^{*}\}}{\min }\{4g(s^t)+2c^{\mathrm{\prime \prime }}{\rho }_{t+1}\}⩽$$ $$\underset{t\in \{1,\mathrm{\dots },t^{*}\}}{\min }\{4{\displaystyle \underset{j=1}{\overset{c_t}{\sum }}}{\gamma }_j+2c^{\mathrm{\prime \prime }}{\gamma }_{c_{t+1}}\}$$

From Formulas (15) and (16) and Lemma 4, we obtain that

(17) $${\displaystyle \frac{g((s^{t^{*}}\setminus e_{b_{t^{*}}(u^{*})j_{t^{*}}})\bigsqcup e_{u^{*}{j}_{u^{*}}})}{g(s^{*})}}⩾$$ $${\displaystyle \frac{{\sum }_{j=1}^{c^{\prime }}{\gamma }_j}{4\underset{t\in \{1,\mathrm{\dots },t^{*}\}}{\min }\left\{\underset{j=1}{\overset{B_t}{\sum }}{\gamma }_j+\frac{c^{\mathrm{\prime \prime }}}{2}{\gamma }_{c_{t+1}}\right\}}}=$$ $${\displaystyle \frac{{\sum }_{j=1}^{c^{\prime }}{\gamma }_j}{4\underset{t\in \{1,\mathrm{\dots },c^{\prime }\}}{\min }\left\{\underset{j=1}{\overset{t-1}{\sum }}{\gamma }_j+\frac{c^{\mathrm{\prime \prime }}}{2}{\gamma }_t\right\}}}⩾$$ $${\displaystyle \frac{1}{4}}\left(1-{\left(1-{\displaystyle \frac{2}{c^{\mathrm{\prime \prime }}}}\right)}^{c^{\prime }}\right)⩾$$ $${\displaystyle \frac{1}{4}}(1-{\text{e}}^{-\frac{2c^{\prime }}{c^{\mathrm{\prime \prime }}}})⩾$$ $${\displaystyle \frac{1}{4}}(1-{\text{e}}^{-2})$$

Then, combing Eqs. ( 8 ) and ( 17 ), we have

(18) $$f(s^{t^{*}})=$$ $$f(s^0)+g(s^{t^{*}})=$$ $$f(s^0)+g((s^{t^{*}}\setminus e_{b_{t^{*}}(u^{*})j_{t^{*}}})\bigsqcup e_{u^{*}{j}_{u^{*}}})-$$ $$[g((s^{t^{*}}\setminus e_{b_{t^{*}}(u^{*})j_{t^{*}}})\bigsqcup e_{u^{*}{j}_{u^{*}}})-g(s^{t^{*}})=$$ $$f(s^0)+g((s^{t^{*}}\setminus e_{b_{t^{*}}(u^{*})j_{t^{*}}})\bigsqcup e_{u^{*}{j}_{u^{*}}})=$$ $$[f((s^{t^{*}}\setminus e_{b_{t^{*}}(u^{*})j_{t^{*}}})\bigsqcup e_{u^{*}{j}_{u^{*}}})-f(s^{t^{*}})]⩾$$ $$f(s^0)+{\displaystyle \frac{1}{4}}(1-{\text{e}}^{-2})g(s^{*})-{\displaystyle \frac{f(s^0)}{2}}⩾$$ $${\displaystyle \frac{1}{4}}(1-{\text{e}}^{-2})f(s^{*})$$

Hence, Algorithm 2 has an approximation ratio of at least ${\displaystyle \frac{1}{4}}(1-{\text{e}}^{-2})$ .

■

In this section, we further give an approximate algorithm for Formula (3) based on Algorithm 2. We assume that $p>1$ is a fixed positive integer.

In order to deal with $p$ matroid constraints, we need to introduce a $p$ -swap to replace the swap in Algorithm 2. We refer to the family of subsets of $E$ whose size does not exceed $p$ as ${[E]}^{⩽p}$ . It should be pointed out that $\mathrm{\varnothing }$ is included in the set ${[E]}^{⩽p}$ . Given a subset $E^{\prime }\subseteq E$ , $u\in E\setminus E^{\prime }$ , and $\bar{y}\in {[E^{\prime }]}^{⩽p}$ , $(u,\bar{y})$ is said to be a $p$ -swap if $(E^{\prime }\setminus \bar{y})$ $\cup \{u\}$ is independent, i.e., $(E^{\prime }\setminus \bar{y})\cup \{u\}\in {\bigcap }_{j=1}^p{ℱ}_j$ . We refer to the collection of $p$ -swaps involving elements in $E^{\prime }$ as $L_p(E^{\prime })$ .

We use the key Lemma 6 to analyze Algorithm 3, similar to Lemma 5 for Algorithm 2.

Lemma 6 ^{[ 6 ]} For any sets $A_1,A_2\in {\bigcap }_{j=1}^p{ℱ}_j$ , we can always construct a mapping $b:A_2\backslash A_1\to {[A_1\backslash A_2]}^{⩽p}$ , where each element $u\in A_2\backslash A_1$ satisfies $(A_1\backslash b(u))\cup \{u\}\in {\bigcap }_{j=1}^p{ℱ}_j$ , and $y\in A_1\backslash A_2$ appears in at most $p$ subsets.

Theorem 3 According to Algorithm 3, a ${\displaystyle \frac{1}{2(p+1)}}\times$ $(1-1/{\text{e}}^{p+1})$ -approximate solution s of Formula (3) can be obtained.

Proof Due to the fact that the constraints are generalized from a single matroid to the intersection of $p$ matroids, we must ensure that the feasible solution $s^t$ in every iteration of Algorithm 3 is an independent set of the intersection of $p$ matroids. Therefore, there are fewer selectable operations $L_p(U(s^t))$ to update $s^t$ . We still check that whether the $p$ -swap is acceptable in Line 8 of Algorithm 3. Then the outputs s need to satisfy that for each $u\in U(s^{*})\setminus U(s)$ , the corresponding $p$ -swap is rejected.

In the following analysis, we need to consider the $p$ -swap involving $U(s^{*})$ in two cases. By Lemma 6 and $U(s)\in {\bigcap }_{j=1}^p{ℱ}_j$ , there exists a $p$ -swap $(u,b(u))\in L_p$ for each $u\in U(s^{*})\setminus U(s)$ .

The classification is similar to Theorem 2.

Case 1: For all elements $u\in U(s^{*})\setminus U(s)$ , the $p$ -swap $(u,b(u))$ satisfied $c_u-c_{b(u)}+c_s⩽c$ . Then the swap $(u,b(u))$ is rejected just because $\rho (u,b(u))⩽0$ . In order to ensure the feasibility of the solution, we use $p$ -swap instead of swap to update the solution s. Then we have

(19) $$f(s^{*})-f(s)⩽$$ $$OP{T}_{f(s^{\prime }\bigsqcup s^0)}(U(s^{*}\setminus s^0)\cup U(s\setminus s^0))-f(s)⩽$$ $$2f(\tilde{s})-f(s)⩽$$ $$2{\displaystyle \underset{e_{ui}⪯\tilde{s}\setminus s}{\sum }}[f(s\bigsqcup e_{ui})-f(s)]+f(s)⩽$$ $${\displaystyle \underset{e_{ui}⪯\tilde{s}\setminus s}{\sum }}2[f((s\setminus ({\bigsqcup }_{b\in b(u)}{e}_{bj}))\bigsqcup e_{ui})-$$ $$f(s\setminus ({\bigsqcup }_{b\in b(u)}{e}_{bj}))]+f(s)⩽$$ $${\displaystyle \underset{e_{ui}⪯\tilde{s}\setminus s}{\sum }}2[f(s)-f(s\setminus ({\bigsqcup }_{b\in b(u)}{e}_{bj}))]+f(s)$$

We still construct $\tilde{s}=s^{\prime }\bigsqcup s^0$ , where $s^{\prime }$ is obtained by Algorithm 1 to maximize $h(s^{\prime })=f(s^{\prime }\bigsqcup s^0)$ over items $U(s^{*}\setminus s^0)\cup U(s\setminus s^0)$ . The generalization of constraints does not affect the derivation of the first three inequalities. Therefore, the order of each element in $U(s)$ is the same as it added to s in Algorithm 3. Then we add elements in $U(s^{*})\setminus U(s)$ in the same order and get $\tilde{s}$ . By Lemmas 2 and 3, we know that $OP{T}_{f(s^{\prime }\bigsqcup s^0)}(U(s^{*}\setminus$ $s^0)\cup U(s\setminus s^0))⩽2f(\tilde{s})$ and $s⪯\tilde{s}$ . The third inequality in Formula (19) is obtained from Lemma 1. The generalization of constraints affects the fourth and the later inequalities. Since swap is generalized to $p$ -swap, we need to remove more points when using orthant submodularity in the fourth inequality in Formula (19). By our assumption about the $p$ -swaps, the last inequality holds.