Maximizing Submodular+Supermodular Functions Subject to a Fairness Constraint

First, we use the greedy algorithm to investigate Formula ( 1 ). In every step, the algorithm enumerates all the elements in the remaining ground set to find the maximum one with the largest marginal increment. Then, the subset to which the selected element belongs is checked. If the constraint of the subset has not reached the capacity, the element is added to the solution set, and is removed away from the ground set. If the constraint of the subset has already reached the capacity, the element cannot be added to the solution set and we delete all the elements in this subset from the ground set. This procedure is repeated until the remaining ground set is empty. Meanwhile, all the constraints are tight. Algorithm 1 gives the pseudo code of this idea.

To analyze the approximation ratio of Algorithm 1, we introduce some notations. Let $O$ denote an optimal solution set of Formula ( 1 ) and $O_j=O\cap E_j$ be the optimal solution in the subset $E_j(j\in [l]).$

Theorem 1 The performance guarantee of Algorithm 1 is $(1-c^g)/(2-c^g).$ The inquiry complexity of Algorithm 1 is $O(nk).$

Proof The final solution $X$ obtained by Algorithm 1 is divided into $X_1,X_2,\mathrm{\dots },X_l$ according to the subsets $E_1,E_2,\mathrm{\dots },E_l$ . Given that $|O_j|=|X_j|=k_j$ , we construct bijections ${\pi }_j:O_j\to X_j$ from $O_j$ to $X_j,j=$ $1,2,\mathrm{\dots },l.$ For $o\in O_j\cap X_j$ , the bijection maps $o$ to itself. The subset $X_j\backslash O_j=\{x_{j_1},x_{j_2},\mathrm{\dots },x_{j_{q_j}}\}$ $(q_j⩽k_j)$ is labeled in the order of the elements added by Algorithm 1. The set $O_j\backslash X_j$ is ordered $\{o_{j_1},o_{j_2},\mathrm{\dots },o_{j_{q_j}}\}$ arbitrary. For $o_{j_i}\in O_j\backslash X_j$ , the bijections are ${\pi }_j(o_{j_i})=x_{j_i},i=1,2,\mathrm{\dots },q_j$ . Let $X^{j_i}$ denote the initial solution of the iteration in which the element $x_{j_i}$ is added. According to Algorithm 1, the equation $h(o_{j_i}|X^{j_i})⩽h(x_{j_i}|X^{j_i})$ holds. Thus, we have

$$\begin{array}{l}h(O)-h(X)\le h(O\cup X)-h(X)\le \\ \frac{1}{1-c^g}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{\displaystyle \underset{i=1}{\overset{q_j}{\sum }}h(o_{j_i}|X^{j_i})}}\le \\ \frac{1}{1-c^g}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{\displaystyle \underset{i=1}{\overset{q_j}{\sum }}h(x_{j_i}|X^{j_i})}}\le \\ \frac{1}{1-c^g}h(X).\end{array}$$

By rearrangement, the above inequality can be written as follows:

(14) $$h(X)\ge \frac{1-c^g}{2-c^g}h(O)$$

The algorithm needs to query the marginal increment of at most $n$ elements in each round, and enumerates $k$ rounds. Thus, we obtain the conclusions in Theorem 1.

■

Remark 1 If $c^g=0,$ then $g(\cdot )$ is a modular function. At this point, Algorithm 1 is guaranteed by 1/2.

In this section, to reduce the inquiry complexity, we propose the threshold greedy algorithm for Formula ( 1 ). The main idea is as follows: when the marginal increment of an element for the current solution is larger than some threshold, it will be added to the solution. Intuitively, the threshold is related to the OPTimal value (OPT). Moreover, the threshold can be considered as one over $k$ of OPT. The OPT can be estimated by using Formula ( 3 ),

(15) $$d\le h(O)\le \frac{1}{1-c^g}{\displaystyle \underset{o\in O}{\sum }h(o)}\le \frac{kd}{1-c^g}$$

where $d={\max }_{e\in E}h(\{e\})$ is the maximum value of any singleton element. Thus, the one over $k$ of OPT falls in the interval $[ϵ{\displaystyle \frac{d}{k}},{\displaystyle \frac{kd}{1-c^g}}]$ , where $ϵ$ is a small positive constant. We reduce from ${\displaystyle \frac{d}{1-c^g}}$ by the order of times the geometric progression ${(1-ϵ)}^{i-1}$ , $\left(i=1,\mathrm{\dots },O\left({\displaystyle \frac{\log k}{ϵ}}\right)\right)$ and consider all these values as thresholds. For each threshold, we enumerate all elements in the ground set. If the marginal increment of an element is larger than the threshold and the corresponding constraint has not reached its upper bound, then the element is added to the solution. More details are shown in Algorithm 2.

To analyze the approximation ratio of the algorithm, we consider the upper bound of the marginal increment for an element which is in the optimal solution but not in the current solution. Suppose that Algorithm 2 is terminated as the threshold lower than $ϵ{\displaystyle \frac{d}{k}}$ . Thus, the solution is updated at most $O\left({\displaystyle \frac{n\log k}{ϵ}}\right)$ times. Let $p=O\left({\displaystyle \frac{n\log k}{ϵ}}\right)$ denote the final step of the iteration. We then have the following lemma.

Lemma 2  Let $x_i(x_i\in E_j(j\in [l]))$ be processed at the $i$ -th iteration $(i=1,\mathrm{\dots },p)$ in Algorithm 2 and $X^{i-1}$ with $|X^{i-1}\cap E_j|<k_j$ be the initial solution for the $i$ -th iteration. $X^i=X^{i-1}\cup \{x_i\}(i=1,\mathrm{\dots },p)$ is the solution after the $i$ -th iteration. For any $o\in$ $O_j\setminus X^{i-1}(j=1\mathrm{\dots },l),$ the relationship between the increment of $o$ to $X^{i-1}$ and the gain at the $i$ -th iteration is given as follows:

(16) $$h(o|X^{i-1})\le \frac{1}{(1-\epsilon )(1-c^g)}h(x_i|X^{i-1})$$

where $o$ and $x_i$ are in the same partition $E_j(j=1,\mathrm{\dots },$ $l)$ .

Proof First, suppose that the threshold is $\theta ={\displaystyle \frac{d}{1-c^g}}$ . Thus, the increment is

$$\begin{array}{l}h(x_i|X^{i-1})\ge \theta =\frac{d}{1-c^g}>\frac{1-\epsilon }{1-c^g}d\ge \\ \frac{1-\epsilon }{1-c^g}h(o)\ge (1-\epsilon )h(o|X^{i-1})\ge \\ (1-\epsilon )(1-c^g)h(o|X^{i-1}),\end{array}$$

where $o\in O\backslash X^{i-1}$ .

Second, for $\theta <{\displaystyle \frac{d}{1-c^g}}$ , suppose that the last threshold is ${\displaystyle \frac{\theta }{1-\epsilon }},$ and $X^m(X^m\subseteq X^{i-1})$ is the last feasible solution with respect to the threshold ${\displaystyle \frac{\theta }{1-\epsilon }}$ . Then, all the elements in the ground set $E$ have been read at least once. For any $o\in O_j\backslash X^{i-1}$ , let $X^{o-1}$ $(|X^{o-1}\cap E_j|<k_j)$ be the initial solution for the iteration to consider the element $o$ . As $o$ has not been added, we therefore have

(17) $$h(o|X^{o-1})\le \frac{\theta }{1-\epsilon }$$

From Formula ( 3 ), we have

(18) $$h(o|X^{i-1})\le \frac{1}{1-c^g}h(o|X^{o-1})$$

where $X^{o-1}\subseteq X^m\subseteq X^{i-1}$ . Meanwhile, from Algorithm 2, at the $i$ -th iteration, we have

(19) $$h(x_i|X^{i-1})\ge \theta$$

Combining Formulas ( 17 )–( 19 ) immediately yields Lemma 4.

■

Theorem 2 Algorithm 2 is guaranteed by ${\displaystyle \frac{{(1+c^g)}^2{(1-ϵ)}^2}{{(1+c^g)}^2{(1-{ϵ}^2)}^2+1}}.$ The inquiry complexity of Algorithm 2 is $O\left({\displaystyle \frac{n\log k}{ϵ}}\right)$ .

Proof From the algorithm, the final output solution $X^p$ satisfies $|X^p|=k$ or $|X^p|<k.$ Let $X_j^p=X^p\cap$ $E_j,j\in [l]$ be the partition of $X^p$ based on $E_j(j\in [l]).$

(1) For the case $|X^p|=k$ , each constraint satisfies $|X^p|=k_j$ . We first label the elements in the set $X_j^p=$ $\{x_{j_1},\mathrm{\dots },x_{j{k}_j}\}$ according to the order of the element added. As $|O_j|=|X_j^p|=k_j$ , we construct bijections ${\pi }_j(i\in [l])$ from $O_j$ to $X_j$ similar as the bijections in the proof of Theorem 1. As a result, we obtain the following:

(20) $${\pi }_j(o_{j_i})=\{\begin{array}{ll}{o}_{j_i},\hfill & \text{if }{o}_{j_i}\in O_j\cap X_j^p;\hfill \\ x_{j_i},\hfill & \text{otherwise}\hfill \end{array}$$

Let $X^{j_i-1}$ be the initial solution of the iteration in which $x_{j_i}$ is added. Thus, we have

(21) $$\begin{array}{l}h(O)-h(X^p)\le \\ h(O\cup X^p)-h(X^P)\le \\ \frac{1}{1-c^g}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{\displaystyle \underset{o_{j_i}\in O_j\backslash X^p}{\sum }h(o_{j_i}|X^{j_i-1})}\le }\\ \frac{1}{{(1-c^g)}^2(1-ϵ)}{\displaystyle \underset{j=1}{\overset{l}{\sum }}{\displaystyle \underset{x_{j_i}\in X_j^p\backslash O_j}{\sum }h(x_{j_i}|X^{j_i-1})\le }}\\ \frac{1}{{(1-c^g)}^2(1-ϵ)}h(X^p)\end{array}$$

The first inequality holds by monotonicity, and the second and the third inequalities hold via Formula ( 3 ) and Lemma 4, respectively. By rearrangement, we obtain

(22) $$h(X^p)\ge \frac{{(1+c^g)}^2(1-ϵ)}{{(1+c^g)}^2(1-ϵ)+1}h(O)$$

(2) In the case $|X^p|<k$ , some constraints satisfy $|X_j^p|<k_j$ , and others satisfy $|X_j^p|=k_j$ . We label the index sets $I_1=\{j||X^p|<k_j,j\in [l]\}$ and $I_2=\{j||X^{p^j}|=k_j,j\in [l]\}$ .

According to Algorithm 2, we have

(23) $$h(o|X^p)<\frac{ϵd}{k}$$

for any $o\in O_j\backslash X^p$ with $j\in I_1$ . Thus, we get

(24) $$\begin{array}{l}{\displaystyle \underset{j\in I_1}{\sum }{\displaystyle \underset{o\in O_j\backslash X^p}{\sum }h(o|X^p)\le ϵh(X^p)\le }}\\ \frac{ϵ}{(1-c^g)(1-ϵ)}h(X^p)\end{array}$$

For the case of $o\in O_j\backslash X^p$ with $j\in I_2$ , we construct bijections similar to Eq. ( 20 ). Thus, we have

(25) $$\begin{array}{l}{\displaystyle \underset{j\in I_2}{\sum }{\displaystyle \underset{o_{j_i}\in O_j\backslash X^p}{\sum }h(o_{j_i}|X^{j_i-1})\le }}\\ \frac{1}{(1-c^g)(1-ϵ)}{\displaystyle \underset{j\in I_2}{\sum }{\displaystyle \underset{x_{j_i}\in X_j^p\backslash O_j}{\sum }h(x_{j_i}|X^{j_i-1})\le }}\\ \frac{1}{(1-c^g)(1-ϵ)}h(X^p)\end{array}$$

Combining Formulas ( 24 ) and ( 25 ), we attain in the following:

$$\begin{array}{l}h(O)-h(X^p)\le \\ h(O\cup X^p)-h(X^p)\le \\ \frac{1}{1-c^g}{\displaystyle \underset{j\in I_1}{\sum }{\displaystyle \underset{o\in O_j\backslash X^p}{\sum }h(o|X^p)+}}\\ \frac{1}{1-c^g}{\displaystyle \underset{j\in I_2}{\sum }{\displaystyle \underset{o_{j_i}\in O_j\backslash X^p}{\sum }h(o_{j_i}|X^{j_i-1})\le }}\\ \frac{1+ϵ}{{(1-c^g)}^2(1-ϵ)}h(X^p).\end{array}$$

By rearrangement, we obtain

(26) $$\begin{array}{l}h(X^p)\ge \frac{{(1+c^g)}^2(1-ϵ)}{{(1+c^g)}^2(1-ϵ)+1+ϵ}h(O)\ge \\ \frac{{(1+c^g)}^2{(1-ϵ)}^2}{{(1+c^g)}^2{(1-ϵ)}^2+1}h(O)\end{array}$$

Combining Formulas ( 22 ) and ( 26 ), we achieve the conclusion in Theorem 2.

■

Remark 2 When $c^g=0,$ $h(\cdot )$ is generated to a submodular function. Thus, Algorithm 2 becomes a $(1/2-ϵ)$ -approximation algorithm.

Finally, we attempt to investigate Formula ( 1 ) with a big data ground set. We cannot store all data information and calculate them simultaneously. We need a streaming algorithm. Streaming algorithms consider the data one by one, and before the next element reveals, it must make a decision for the current one. Four indexes are used to measure the performance of a streaming algorithm. The approximation ratio and time complexity are formal indexes. The other two are memory complexity and the number of passes of reading the total data. We aspire to attain a one-pass streaming algorithm with a reasonable approximation ratio, time complexity and memory complexity.

Similar to the threshold greedy algorithm, if the marginal increment of the current element is larger than the threshold, then it is added to the solution. We subdivide the estimation interval of the OPT by geometric series, and consider all these values as the threshold. By Formula ( 15 ), the bound of the OPT is as follows:

(27) $$\eta \le h(O)\le \frac{kd}{1-c^g}$$

where $\eta =\max [d,h(X)]$ .

We subdivide the interval $[\eta ,{\displaystyle \frac{2kd}{1-c^g}}]$ and obtain a set in the following:

$$\mathcal{H}=\left\{{(1+ϵ)}^m|m\in Z,\max \{d,\eta \}\le {(1+ϵ)}^m\le \frac{2kd}{1-c^g}\right\}.$$

Suppose that ${(1+ϵ)}^m=h(O).$ Then, we attain $m^{*}=\lfloor {\displaystyle \frac{\log h(O)}{\log (1+\epsilon )}}\rfloor$ . Let ${\tau }^{\ast }={(1+ϵ)}^{m^{*}}$ . Evidently, we have ${\tau }^{*}⩽h(O)$ . Meanwhile, ${\tau }^{*}⩾{\displaystyle \frac{h(O)}{1+ϵ}}⩾(1-$ $ϵ)h(O).$ Therefore, the parameter ${\tau }^{*}$ is contained in $\mathscr{H}$ with $(1-ϵ)h(O)⩽{\tau }^{*}⩽h(O)$ . ${\tau }^{*}$ can be considered as an estimation of the OPT.

As the element is revealed one by one in streaming algorithms, we cannot obtain the maximum value $d$ of a singleton element in advance. Meanwhile, the feasible solution is updated with the new arriving element. Thus, the estimation interval and the parameter set $\mathscr{H}$ are updated. Finally, the set desired is exactly ${\mathscr{H}}_n$ with $(1-ϵ)h(O)⩽{\tau }^{*}⩽h(O).$

Another difficulty is that $c^g$ is the total curvature of the supermodular function $g(\cdot )$ , whose computation needs the entire information of the data set. Thus, we cannot receive it in advance. Given that $c^g\in [0,1)$ , we refine the interval [0, 1) into $\lfloor 1/ϵ\rfloor$ copies to simulate the value $c^g$ . The more copies of the interval $[0,1)$ are subdivided, the higher accuracy of the solution can be achieved. Finally, the algorithm returns a solution with the largest value among all these $c^g\in \{0,ϵ,2ϵ,\mathrm{\dots },\lfloor 1/ϵ\rfloor ϵ\}$ and $\tau$ in ${\mathscr{H}}_n$ . The pseudo code of the one-pass streaming algorithm is presented in Algorithm 3.

In the following lemma, we consider the properties of the solution $X_{r^{*}}$ corresponding to ${\tau }^{*}$ in the set $𝒳$ , where $𝒳=\{X_{\tau },\tau \in {\mathscr{H}}_n\}$ is the set of all final solutions with respect to the parameters $\tau \in {\mathscr{H}}_n\}$ returned by the streaming processing and $(1-ϵ)h(O)⩽{\tau }^{*}⩽h(O)$ . The constraints of $X_{{\tau }^{*}}$ may result in (1) $|X_{{\tau }^{*}}\cap E_j|=k_j$ for all $j\in [l]$ , or (2) $|X_{{\tau }^{*}}\cap E_j|<k_j$ for all $j\in [l],$ or (3) $|X_{{\tau }^{*}}\cap E_j|=k_j$ for some $j$ and $|X_{{\tau }^{*}}\cap E_j|<k_j$ for others. One of these three cases may occur.

Lemma 3 For the parameter ${\tau }^{\ast }$ with $(1-ϵ)h(O)⩽$ ${\tau }^{*}⩽h(O),$ if the cardinality of $X_{{\tau }^{*}}$ is $|X_{{\tau }^{*}}|=k$ , or $|X_{{\tau }^{*}}\cap E_j|<k_j$ for all $j\in [l],$ we have $h(X_{{\tau }^{*}})⩾$ $\left(1-{\displaystyle \frac{1}{2(1-c^g)}}-ϵ\right)h(O).$

Proof By mathematical induction, we get

$$h(X_{\tau *})\ge \frac{\tau *}{2k}\left|X_{\tau *}\right|.$$

For the case of $|X_{{\tau }^{*}}|=k$ , it is obvious that

$$h(X_{\tau *})\ge \frac{\tau *}{2}\ge \frac{1}{2}(1-ϵ)h(O).$$

For the case that $|X_{{\tau }^{*}}\cap E_j|<k_j$ for all $j\in [l],$ we have

$$\begin{array}{l}h(O)-h(X_{\tau *})\le h(O\cup X_{\tau *})-h(X_{\tau *})\le \\ \frac{1}{1-c^g}{\displaystyle \underset{o\in O\backslash X_{\tau *}}{\sum }h(o|X_{\tau *})\le }\\ \frac{1}{1-c^g}\cdot \frac{\tau *}{2k}\cdot k\le \frac{1}{2(1-c^g)}h(O),\end{array}$$

where the third inequality holds by Algorithm 3.

By rearrangement, we get

(28) $$h(X_{\tau *})\ge \left(1-\frac{1}{2(1-c^g)}\right)h(O)$$

From the above, we receive the conclusions in Lemma 5.

■

However, if the constraints of $X_{{\tau }^{*}}$ are $X_{{\tau }^{*}}\cap E_j|=k_j$ for some $j$ and $|X_{{\tau }^{*}}\cap E_j|<k_j$ for others, we cannot achieve the quality of $X_{{\tau }^{*}}$ . Thus, Algorithm 3 employs a post-processing to improve the solution quality and help us achieve an approximation ratio of the algorithm. We keep some elements during the streaming processing and store them in set $M$ . The marginal increments of these elements are less than the threshold ${\displaystyle \frac{\tau }{2k}}$ but no less than ${\displaystyle \frac{\beta \eta }{2k}}$ . Set $M$ is considered as the ground set in the post-processing. The solutions $X_{\phi }$ based on the special parameter $\phi$ are considered. Two cases are investigated. One is when $\phi$ is assigned as the minimum value in set $\mathrm{\Omega }=\{\tau :X_{\tau }(E_j)<k_j\}$ for all $j\in [l],X_{\tau }\in 𝒳\},$ if $\mathrm{\Omega }\ne \mathrm{\varnothing }$ . If $\mathrm{\Omega }=\mathrm{\varnothing }$ , then $\phi$ is the maximum value in set ${\mathscr{H}}_n$ . We consider the properties of the final solution $X_{\phi }^f$ whose initial solution is $X_{\phi }$ in the post-processing.

Theorem 3 Algorithm 3 is guaranteed by ${\displaystyle \frac{2{(1-c^g)}^2-\beta }{2{(1-c^g)}^2+2+2ϵ}}$ , the update time per element in streaming processing is $O\left({\displaystyle \frac{\log k}{ϵ}}\right),$ and the running time for the post-processing is $O\left({\displaystyle \frac{k\log k}{ϵ}}(|M|+k)\right).$

Proof We first consider the case that $|X_{\phi }\cap E_j|<k_j$ for all $j\in [l].$

In this case, we divide $O\backslash X_{\phi }^f$ into two sets: $O_I=$ $\left(O\backslash X_{\phi }^f\right)\cap M,$ in which the optimal elements are in the set $M$ , but not in the final solution $X_{\phi }^f$ ; $O_J=$ $\left(O\backslash X_{\phi }^f\right)\cap (E\backslash M)$ , in which the optimal elements are deleted directly during streaming processing.

For any $o\in O_I$ , we have

(29) $$h(o|X_{\phi }^f)\le \frac{1}{1-c^g}h(o|{X^{\prime }}_{\phi })\le \frac{1}{1-c^g}h(x|{X^{\prime }}_{\phi })$$

where $X_{\phi }^{\prime }(X_{\phi }^{\prime }\subseteq X_{\phi }^f)$ is the initial solution when $x$ is added, and $x$ and $o$ are in the same patition. Formula ( 29 ) holds both in streaming processing $(h(o|X_{\phi }^{\prime })<{\displaystyle \frac{\phi }{2k}}⩽$ $h(x|X_{\phi }^{\prime }))$ and in post processing (the idea of greedy $(h(o|X_{\phi }^{\prime })⩽h(x|X_{\phi }^{\prime }))$ .

Meanwhile, as the element $o\in O_J$ is deleted during streaming processing, its marginal increment to the corresponding solution $X_{\phi }^o$ is less than ${\displaystyle \frac{\beta \eta }{2k}}$ . Thus, for any $o\in O_J$ , we achieve

(30) $$h(o|X_{\phi }^f)\le \frac{1}{1-c^g}h(o|X_{\phi }^o)<\frac{1}{1-c^g}\cdot \frac{\beta \eta }{2k}$$

Combining Formulas ( 29 ) and ( 30 ), we have

(31) $$\begin{array}{l}h(O)-h(X_{\phi }^f)\le \\ h(O\cup X_{\phi }^f)-h(X_{\phi }^f)\le \\ \frac{1}{1-c^g}{\displaystyle \underset{o\in O\backslash X_{\phi }^f}{\sum }h(o|X_{\phi }^f)=}\\ \frac{1}{1-c^g}\left({\displaystyle \underset{o\in O_I}{\sum }h(o|X_{\phi }^f)+{\displaystyle \underset{o\in O_J}{\sum }h(o|X_{\phi }^f)}}\right)\le \\ \frac{1}{1-c^g}\left(\frac{1}{1-c^g}{\displaystyle \underset{x\in X_{\phi }^f}{\sum }h(x|{X^{\prime }}_{\phi })+\frac{1}{1-c^g}\cdot \frac{k\beta \eta }{2k}}\right)\le \\ \frac{1}{{(1-c^g)}^2}\left(h(X_{\phi }^f)+\frac{\beta }{2}h(O)\right)\end{array}$$

where $X_{\phi }^{\prime }$ is the initial solution when $x$ is added.

By rearrangement, we obtain

(32) $$h(X_{\phi }^f)\ge \frac{2{(1-c^g)}^2-\beta }{2{(1-c^g)}^2+2}h(O)$$

Second, we investigate the case in which $\phi$ is the maximum parameter in ${\mathscr{H}}_n$ . Notably, $\phi ⩽{\displaystyle \frac{2kd}{1-c^g}}⩽$ $(1+ϵ)\phi$ . In such situation, for any solution $X_r(\tau \in {\mathscr{H}}_n)$ , there are at least one element in the set $\{j||X_r\cap$ $E_j|=k_j,j\in [l]\}$ .

In this case, $O\backslash X_{\phi }^f$ is divided into three sets: $O_{J_1}$ in which the optimal elements are deleted in the streaming process since their corresponding partitions have already reached the capacities, where $J_1=\{j||X_{\phi }\cap E_j|=$ $k_j,j\in [l]\};O{}_{J_2}=(O\backslash (X_{\phi }^f\cup O_{J_1}))\cap M,$ in which the optimal elements are in the set $M$ but not in the final solution $X_{\phi }^f$ ; $O_{J_3}=\left(O\backslash \left(X_{\phi }^f\cup O_{J_1}\right)\right)\cap (E\backslash M),$ in which the optimal elements are deleted directly during streaming processing thought the constraints of their corresponding partitions are not tight. However, their marginal increments are less than ${\displaystyle \frac{\beta \eta }{2k}}.$

For $o\in O_{J_1}$ , we have

$$\begin{array}{ll}h(o|X_{\phi }^f)\le \hfill & \frac{1}{1-c^g}h(o)\le \frac{1}{1-c^g}d=\hfill \\ \hfill & \frac{2k}{1-c^g}d\cdot \frac{1}{2k}\le \frac{(1+ϵ)\phi }{2k}\le \hfill \\ \hfill & (1+ϵ)h(x|{X^{\prime }}_{\phi })\le \frac{1+ϵ}{1-c^g}h(x|{X^{\prime }}_{\phi }),\hfill \end{array}$$

where $x$ is in the same partition with $o$ and $X_{\phi }^{\prime }$ is the initial solution when $x$ is added. Collect all these $x$ in the set $X_{J_1}=\{x:x\in X_{\phi }^f\backslash E_j$ , $j\in J_1\}$ .

For $o\in O_{J_1}$ and $o\in O_{J_3}$ , the relations are similar with Formulas ( 29 ) and ( 30 ).

Thus, we obtain the calculation as follows:

$$\begin{array}{l}h(O)-h(X_{\phi }^f)\le \\ h(O\cup X_{\phi }^f)-h(X_{\phi }^f)\le \\ \frac{1}{1-c^g}{\displaystyle \underset{o\in O\backslash X_{\phi }^f}{\sum }h(o|X_{\phi }^f)=}\\ \frac{1}{1-c^g}\left({\displaystyle \underset{o\in O_{J_1}}{\sum }+{\displaystyle \underset{o\in O_{J_2}}{\sum }+{\displaystyle \underset{o\in O_{J_3}}{\sum }}}}\right)h(o|X_{\phi }^f)\le \\ \frac{1}{{(1-c^g)}^2}((1+ϵ){\displaystyle \underset{x\in X_{J_1}}{\sum }h(x|{X^{\prime }}_{\phi })+}\\ {\displaystyle \underset{x\in X_{\phi }^f\backslash X_{J_1}}{\sum }h(x|{X^{\prime }}_{\phi })+\frac{k\beta \eta }{2k}})\le \\ \frac{1}{{(1-c^g)}^2}\left((1+ϵ)h(X_{\phi }^f)+\frac{\beta }{2}h(O)\right).\end{array}$$

By rearrangement, we have

(33) $$h(X_{\phi }^f)\ge \frac{2{(1-c^g)}^2-\beta }{2{(1-c^g)}^2+2+2ϵ}h(O)$$

Combining Formulas ( 32 ) and ( 33 ), we obtain the conclusion in Theorem 5.

From $d{(1+ϵ)}^m={\displaystyle \frac{2kd}{1-c^g}}$ , the cardinality of the set ${\mathscr{H}}_n$ is $O\left({\displaystyle \frac{\log k}{ϵ}}\right)$ . Therefore, in the streaming processing the memory complexity is $O\left({\displaystyle \frac{k\log k}{ϵ}}\right)$ for each $c^g$ . At most $(|M|+k)$ elements are stored for the post-processing. As we have to check $\lfloor 1/ϵ\rfloor$ values of $c^g$ , the total memory of Algorithm 3 is $O\left({\displaystyle \frac{k\log k}{{ϵ}^2}}+{\displaystyle \frac{|M|}{ϵ}}\right).$ In the streaming process, the inquiry complexity for each element is formed by the number of parameters in set ${\mathscr{H}}_n$ , that is $O\left({\displaystyle \frac{\log k}{ϵ}}\right)$ . In the post-processing, the algorithm enumerates at most $k$ iterations for $|M|+k$ elements with each initial solution. Thus, post-processing needs $O\left({\displaystyle \frac{k\log k}{ϵ}}(|M|+k)\right).$ oracle queries for each $c^g$ .