Streaming Algorithms for Non-Submodular Maximization on the Integer Lattice

In the streaming model, we cannot decide immediately whether the value of the arriving element exceeds the maximum marginal value over each iteration. A natural idea is to compare the marginal gain produced by the arriving element with OPT in a certain way. To determine whether or not the arriving item $e$ is selected, a specified threshold of $\frac{{\gamma }_{{}_f}v/2^{{\gamma }_{{}_f}}-f(\text{𝒔})}{k-\text{𝒔}(G)}$ is used. We combine the exponential growth method for estimating the OPT with binary search to give the $\min \{(1-\epsilon ){\gamma }_{{}_f}/2^{{\gamma }_{{}_f}},\text{( 1 - 1 /}{\gamma }_{{}_f}^w{2}^{{\gamma }_{{}_f}})\}$ -approximation algorithm for NMCC. The detailed description refers to Algorithms 1 and 2 below.

Lemma 1 Suppose ${\text{𝒔}}_i$ is the output of the $i$ -th iteration in Algorithm 2, then we have

(2) $$f({\text{𝒔}}_i)⩾{\displaystyle \frac{{\gamma }_{{}_f}v{\text{𝒔}}_i(G)}{2^{{\gamma }_{{}_f}}k}}$$

Proof From Algorithm 2, we know the initial vector ${\text{𝒔}}_0=\text{𝟎}$ , so Formula (2) holds naturally. Then, we assume that Formula (2) holds for the $i$ -th iteration; we only need to prove that it holds for the $(i+1)$ -th iteration. If we let ${\alpha }_{i+1}$ be the output returned from Algorithm 1, then we have

$$f({\text{𝒔}}_i+{\alpha }_{i+1}{\chi }_{e_{i+1}})=f({\alpha }_{i+1}{\chi }_{e_{i+1}}|{\text{𝒔}}_i)+f({\text{𝒔}}_i)⩾$$ $$\mathrm{\hspace{1em}}{\displaystyle \frac{{\alpha }_{i+1}(\frac{{\gamma }_{{}_f}v}{2^{{\gamma }_{{}_f}}}-f({\text{𝒔}}_i))}{k-{\text{𝒔}}_i(G)}}+f({\text{𝒔}}_i)⩾$$ $${\displaystyle \frac{{\alpha }_{i+1}\times {\gamma }_{{}_f}v}{2^{{\gamma }_{{}_f}}(k-{\text{𝒔}}_i(G))}}+{\displaystyle \frac{k-{\text{𝒔}}_i(G)-{\alpha }_{i+1}}{k-{\text{𝒔}}_i(G)}}f({\text{𝒔}}_i).$$

Together with the introduced hypothesis, we conclude that

$$f({\text{𝒔}}_i+{\alpha }_{i+1}{\chi }_{e_{i+1}})⩾$$ $${\displaystyle \frac{{\alpha }_{i+1}{\gamma }_{f}v}{2^{{\gamma }_f}(k-{\text{𝒔}}_i(G))}}+{\displaystyle \frac{k-{\text{𝒔}}_i(G)-{\alpha }_{i+1}}{k-{\text{𝒔}}_i(G)}}\times {\displaystyle \frac{{\gamma }_{f}v{\text{𝒔}}_i(G)}{2^{{\gamma }_f}k}}=$$ $${\displaystyle \frac{{\gamma }_{f}v(k-{\text{𝒔}}_i(G))({\text{𝒔}}_i(G)+{\alpha }_{i+1})}{2^{{\gamma }_f}k(k-{\text{𝒔}}_i(G))}}=$$ $${\displaystyle \frac{{\gamma }_{f}v}{2^{{\gamma }_f}k}}({\text{𝒔}}_i(G)+{\alpha }_{i+1})=$$ $${\displaystyle \frac{{\gamma }_{f}v}{2^{{\gamma }_f}k}}{\text{𝒔}}_{i+1}(G),$$

which completes the proof.

■

In the following Lemma 2, we consider the marginal increment of ${\chi }_e$ with $e\in \{{\text{𝒔}}^{*}\}\setminus \{\widetilde{\text{𝒔}}\}$ .

Lemma 2 Suppose $\widetilde{\text{𝒔}}$ is the final output of Algorithm 2 and $\widetilde{\text{𝒔}}(G)<k$ , then we have

$$f({\chi }_e|\widetilde{\text{𝒔}})<\frac{v}{2^{{\gamma }_f}k},$$

where $e\in \{{\text{𝒔}}^{*}\}\setminus \{\widetilde{\text{𝒔}}\}$ .

Proof Assume that Algorithm 2 produces a vector ${\text{𝒔}}_e^{\prime }$ right before the element $e$ ’s arrival. ${\alpha }_e$ is the output of the BinarySearch subroutine satisfying the following two inequations:

(3) $${\displaystyle \frac{f({\alpha }_e{\chi }_e|{\text{𝒔}}_e^{\prime })}{{\alpha }_e}}⩾{\displaystyle \frac{{\gamma }_{f}v/2^{{\gamma }_f}-f({\text{𝒔}}_e^{\prime })}{k-{\text{𝒔}}_e(G)}}$$

and

(4) $${\displaystyle \frac{f(({\alpha }_e+1){\chi }_e|{\text{𝒔}}_e^{\prime })}{{\alpha }_e+1}}<{\displaystyle \frac{{\gamma }_{f}v/2^{{\gamma }_f}-f({\text{𝒔}}_e^{\prime })}{k-{\text{𝒔}}_e(G)}}$$

Let ${\text{𝒔}}_e={\text{𝒔}}_e^{\prime }+{\alpha }_e{\chi }_e⩽\widetilde{\text{𝒔}}$ . Therefore,

(5) $$f({\chi }_e|\widetilde{\text{𝒔}})⩽$$ $${\displaystyle \frac{1}{{\gamma }_f}}f({\chi }_e|{\text{𝒔}}_e)=$$ $${\displaystyle \frac{1}{{\gamma }_f}}f({\chi }_e|{\text{𝒔}}_e^{\prime }+{\alpha }_e{\chi }_e)=$$ $${\displaystyle \frac{1}{{\gamma }_f}}[f({\text{𝒔}}_e^{\prime }+({\alpha }_e+1){\chi }_e)-f({\text{𝒔}}_e^{\prime }+{\alpha }_e{\chi }_e)]=$$ $${\displaystyle \frac{1}{{\gamma }_f}}[f({\text{𝒔}}_e^{\prime }+({\alpha }_e+1){\chi }_e)-f({\text{𝒔}}_e^{\prime })+f({\text{𝒔}}_e^{\prime })-$$ $$\mathrm{\hspace{1em}}f({\text{𝒔}}_e^{\prime }+{\alpha }_e{\chi }_e)]=$$ $${\displaystyle \frac{1}{{\gamma }_f}}[f(({\alpha }_e+1){\chi }_e|{\text{𝒔}}_e^{\prime })-f({\alpha }_e{\chi }_e|{\text{𝒔}}_e^{\prime })]<$$ $${\displaystyle \frac{1}{{\gamma }_f}}[({\alpha }_e+1){\displaystyle \frac{{\gamma }_{f}v/2^{{\gamma }_f}-f({\text{𝒔}}_e^{\prime })}{k-{\text{𝒔}}_e(G)}}-$$ $$\mathrm{\hspace{1em}}{\alpha }_e{\displaystyle \frac{{\gamma }_{f}v-2^{{\gamma }_f}f({\text{𝒔}}_e^{\prime })}{2^{{\gamma }_f}(k-{\text{𝒔}}_e(G))}}]<$$ $${\displaystyle \frac{1}{{\gamma }_f}}{\displaystyle \frac{{\gamma }_{f}v-2^{{\gamma }_f}f({\text{𝒔}}_e^{\prime })}{2^{{\gamma }_f}(k-{\text{𝒔}}_e(G))}}⩽$$ $${\displaystyle \frac{1}{{\gamma }_f}}{\displaystyle \frac{{\gamma }_{f}v-{\gamma }_{f}v\cdot {\text{𝒔}}_e(G)}{2^{{\gamma }_f}(k-{\text{𝒔}}_e(G))}}={\displaystyle \frac{v}{2^{{\gamma }_f}k}}$$

This completes the proof.

■

Based on the Lemmas 1 and 2, we can analyze the performance of Algorithm 2. In the analysis, Lemma 1 is used for the case $\text{𝒔}(G)=k$ , and Lemma 2 is used for the case $\text{𝒔}(G)<k$ .

Theorem 1 For any $\epsilon \in (0,1)$ and given function $f\in F_{𝒄}$ , Algorithm 2 is a two-pass algorithm, the approximation is $\min \{(1-\epsilon ){\gamma }_f/2^{{\gamma }_f},(1-1/{\gamma }_f^w{2}^{{\gamma }_f})\}$ , the memory complexity is $O(\frac{k}{\epsilon }\log \frac{k}{\epsilon })$ , and the query times per element is $O(\frac{\log k}{\epsilon }\log \frac{\log k}{\epsilon })$ .

Proof Suppose ${\text{𝒔}}^{*}=\underset{e\in \{{\text{𝒔}}^{*}\}}{\sum }{\chi }_e$ . From the definition of the DR ratio, we obtain

$$OPT=f({\text{𝒔}}^{*})=f\left({\displaystyle \underset{e\in \{{\text{𝒔}}^{*}\}}{\sum }}{\chi }_e\right)⩽$$ $$\mathrm{\hspace{1em}}\mathit{\hspace{1em}}{\displaystyle \frac{1}{{\gamma }_f}}{\displaystyle \underset{e\in \{{\text{𝒔}}^{*}\}}{\sum }}f({\chi }_e)⩽{\displaystyle \frac{k\cdot m}{{\gamma }_f}}.$$

Moreover,

(6) $$m=\underset{e\in G}{\max }f({\chi }_e)⩽f({\text{𝒔}}^{*})$$

Combined Formulas (5) and (6), we have

$$m⩽OPT⩽\frac{k\cdot m}{{\gamma }_f}.$$

Let $\bar{i}=\lfloor {\log }_{1+\epsilon }OPT\rfloor$ , thus there exists $v={(1+\epsilon )}^{\bar{i}}$ , such that $v⩽OPT$ and

(7) $$v⩾{\displaystyle \frac{OPT}{1+\epsilon }}⩾\max \{(1-\epsilon )OPT,{\displaystyle \frac{m}{1+\epsilon }}\}$$

From Formulas (6) and (7), we obtain

$$v\in [(1-\epsilon )OPT,OPT].$$

Next, for $v\in V_{\epsilon }$ , we denote ${\text{𝒔}}^v$ as the output of Algorithm 2, and consider the following two cases:

(1) ${\text{𝒔}}^v(G)=k$

According to Lemma 1, we have

(8) $$f({\text{𝒔}}^v)⩾{\displaystyle \frac{{\gamma }_{f}v{\text{𝒔}}^v(G)}{2^{{\gamma }_f}k}}={\displaystyle \frac{(1-\epsilon ){\gamma }_f}{2^{{\gamma }_f}}}OPT$$

(2) ${\text{𝒔}}^v(G)<k$

From Lemma 2 and the weak DR ratio, we have

$$f({\text{𝒔}}^{*}\cup {\text{𝒔}}^v)-f({\text{𝒔}}^v)⩽$$ $${\displaystyle \frac{1}{{\gamma }_f^w}}{\displaystyle \underset{e\in suu{p}^{+}\{{\text{𝒔}}^{*}-{\text{𝒔}}^v\}}{\sum }}f(({\text{𝒔}}^{*}-{\text{𝒔}}^v)(e){\chi }_e|{\text{𝒔}}^v)⩽$$ $${\displaystyle \frac{1}{{\gamma }_f^w}}{\displaystyle \underset{e\in \{{\text{𝒔}}^{*}\}\setminus \{{\text{𝒔}}^v\}}{\sum }}f({\chi }_e|{\text{𝒔}}^v)<$$ $${\displaystyle \frac{1}{{\gamma }_f^w}}{\displaystyle \underset{e\in \{{\text{𝒔}}^{*}\}\setminus \{{\text{𝒔}}^v\}}{\sum }}{\displaystyle \frac{v}{2^{{\gamma }_f}k}}⩽$$ $${\displaystyle \frac{v}{{\gamma }_f^w{2}^{{\gamma }_f}}}⩽{\displaystyle \frac{OPT}{{\gamma }_f^w{2}^{{\gamma }_f}}}.$$

As $f({\text{𝒔}}^{*}\cup {\text{𝒔}}^v)-f({\text{𝒔}}^v)⩾OPT-f({\text{𝒔}}^v)$ , we obtain

(9) $$f({\text{𝒔}}^v)⩾(1-{\displaystyle \frac{1}{{\gamma }_f^w{2}^{{\gamma }_f}}})OPT$$

Combining Formulas (8) and (9), we obtain

$$f({\text{𝒔}}^v)⩾\min \{\frac{(1-\epsilon ){\gamma }_f}{2^{{\gamma }_f}},1-\frac{1}{{\gamma }_f^w{2}^{{\gamma }_f}}\}OPT.$$

From Algorithm 2, we know that $\widetilde{\text{𝒔}}=\arg \underset{v\in V_{\epsilon }}{\max }f({\text{𝒔}}^v)$ . Thus, we can conclude that

$$f(\widetilde{\text{𝒔}})⩾f({\text{𝒔}}^v)⩾\min \{\frac{(1-\epsilon ){\gamma }_f}{2^{{\gamma }_f}},1-\frac{1}{{\gamma }_f^w{2}^{{\gamma }_f}}\}OPT$$

The proof is completed.

■

In the streaming model, we cannot decide immediately whether the value of the arriving element exceeds the maximum marginal value over each iteration. A natural idea is to compare the marginal gain produced by the arriving element with OPT in a certain way. To determine whether or not the arriving item $e$ is selected, a specified threshold of $\frac{{\gamma }_{{}_f}v/2^{{\gamma }_{{}_f}}-f(\text{𝒔})}{k-\text{𝒔}(G)}$ is used. We combine the exponential growth method for estimating the OPT with binary search to give the $\min \{(1-\epsilon ){\gamma }_{{}_f}/2^{{\gamma }_{{}_f}},\text{( 1 - 1 /}{\gamma }_{{}_f}^w{2}^{{\gamma }_{{}_f}})\}$ -approximation algorithm for NMCC. The detailed description refers to Algorithms 1 and 2 below.

Lemma 1 Suppose ${\text{𝒔}}_i$ is the output of the $i$ -th iteration in Algorithm 2, then we have

(2) $$f({\text{𝒔}}_i)⩾{\displaystyle \frac{{\gamma }_{{}_f}v{\text{𝒔}}_i(G)}{2^{{\gamma }_{{}_f}}k}}$$

Proof From Algorithm 2, we know the initial vector ${\text{𝒔}}_0=\text{𝟎}$ , so Formula (2) holds naturally. Then, we assume that Formula (2) holds for the $i$ -th iteration; we only need to prove that it holds for the $(i+1)$ -th iteration. If we let ${\alpha }_{i+1}$ be the output returned from Algorithm 1, then we have

$$f({\text{𝒔}}_i+{\alpha }_{i+1}{\chi }_{e_{i+1}})=f({\alpha }_{i+1}{\chi }_{e_{i+1}}|{\text{𝒔}}_i)+f({\text{𝒔}}_i)⩾$$ $$\mathrm{\hspace{1em}}{\displaystyle \frac{{\alpha }_{i+1}(\frac{{\gamma }_{{}_f}v}{2^{{\gamma }_{{}_f}}}-f({\text{𝒔}}_i))}{k-{\text{𝒔}}_i(G)}}+f({\text{𝒔}}_i)⩾$$ $${\displaystyle \frac{{\alpha }_{i+1}\times {\gamma }_{{}_f}v}{2^{{\gamma }_{{}_f}}(k-{\text{𝒔}}_i(G))}}+{\displaystyle \frac{k-{\text{𝒔}}_i(G)-{\alpha }_{i+1}}{k-{\text{𝒔}}_i(G)}}f({\text{𝒔}}_i).$$

Together with the introduced hypothesis, we conclude that

$$f({\text{𝒔}}_i+{\alpha }_{i+1}{\chi }_{e_{i+1}})⩾$$ $${\displaystyle \frac{{\alpha }_{i+1}{\gamma }_{f}v}{2^{{\gamma }_f}(k-{\text{𝒔}}_i(G))}}+{\displaystyle \frac{k-{\text{𝒔}}_i(G)-{\alpha }_{i+1}}{k-{\text{𝒔}}_i(G)}}\times {\displaystyle \frac{{\gamma }_{f}v{\text{𝒔}}_i(G)}{2^{{\gamma }_f}k}}=$$ $${\displaystyle \frac{{\gamma }_{f}v(k-{\text{𝒔}}_i(G))({\text{𝒔}}_i(G)+{\alpha }_{i+1})}{2^{{\gamma }_f}k(k-{\text{𝒔}}_i(G))}}=$$ $${\displaystyle \frac{{\gamma }_{f}v}{2^{{\gamma }_f}k}}({\text{𝒔}}_i(G)+{\alpha }_{i+1})=$$ $${\displaystyle \frac{{\gamma }_{f}v}{2^{{\gamma }_f}k}}{\text{𝒔}}_{i+1}(G),$$

which completes the proof.

■

In the following Lemma 2, we consider the marginal increment of ${\chi }_e$ with $e\in \{{\text{𝒔}}^{*}\}\setminus \{\widetilde{\text{𝒔}}\}$ .

Lemma 2 Suppose $\widetilde{\text{𝒔}}$ is the final output of Algorithm 2 and $\widetilde{\text{𝒔}}(G)<k$ , then we have

$$f({\chi }_e|\widetilde{\text{𝒔}})<\frac{v}{2^{{\gamma }_f}k},$$

where $e\in \{{\text{𝒔}}^{*}\}\setminus \{\widetilde{\text{𝒔}}\}$ .

Proof Assume that Algorithm 2 produces a vector ${\text{𝒔}}_e^{\prime }$ right before the element $e$ ’s arrival. ${\alpha }_e$ is the output of the BinarySearch subroutine satisfying the following two inequations:

(3) $${\displaystyle \frac{f({\alpha }_e{\chi }_e|{\text{𝒔}}_e^{\prime })}{{\alpha }_e}}⩾{\displaystyle \frac{{\gamma }_{f}v/2^{{\gamma }_f}-f({\text{𝒔}}_e^{\prime })}{k-{\text{𝒔}}_e(G)}}$$

and

(4) $${\displaystyle \frac{f(({\alpha }_e+1){\chi }_e|{\text{𝒔}}_e^{\prime })}{{\alpha }_e+1}}<{\displaystyle \frac{{\gamma }_{f}v/2^{{\gamma }_f}-f({\text{𝒔}}_e^{\prime })}{k-{\text{𝒔}}_e(G)}}$$

Let ${\text{𝒔}}_e={\text{𝒔}}_e^{\prime }+{\alpha }_e{\chi }_e⩽\widetilde{\text{𝒔}}$ . Therefore,

(5) $$f({\chi }_e|\widetilde{\text{𝒔}})⩽$$ $${\displaystyle \frac{1}{{\gamma }_f}}f({\chi }_e|{\text{𝒔}}_e)=$$ $${\displaystyle \frac{1}{{\gamma }_f}}f({\chi }_e|{\text{𝒔}}_e^{\prime }+{\alpha }_e{\chi }_e)=$$ $${\displaystyle \frac{1}{{\gamma }_f}}[f({\text{𝒔}}_e^{\prime }+({\alpha }_e+1){\chi }_e)-f({\text{𝒔}}_e^{\prime }+{\alpha }_e{\chi }_e)]=$$ $${\displaystyle \frac{1}{{\gamma }_f}}[f({\text{𝒔}}_e^{\prime }+({\alpha }_e+1){\chi }_e)-f({\text{𝒔}}_e^{\prime })+f({\text{𝒔}}_e^{\prime })-$$ $$\mathrm{\hspace{1em}}f({\text{𝒔}}_e^{\prime }+{\alpha }_e{\chi }_e)]=$$ $${\displaystyle \frac{1}{{\gamma }_f}}[f(({\alpha }_e+1){\chi }_e|{\text{𝒔}}_e^{\prime })-f({\alpha }_e{\chi }_e|{\text{𝒔}}_e^{\prime })]<$$ $${\displaystyle \frac{1}{{\gamma }_f}}[({\alpha }_e+1){\displaystyle \frac{{\gamma }_{f}v/2^{{\gamma }_f}-f({\text{𝒔}}_e^{\prime })}{k-{\text{𝒔}}_e(G)}}-$$ $$\mathrm{\hspace{1em}}{\alpha }_e{\displaystyle \frac{{\gamma }_{f}v-2^{{\gamma }_f}f({\text{𝒔}}_e^{\prime })}{2^{{\gamma }_f}(k-{\text{𝒔}}_e(G))}}]<$$ $${\displaystyle \frac{1}{{\gamma }_f}}{\displaystyle \frac{{\gamma }_{f}v-2^{{\gamma }_f}f({\text{𝒔}}_e^{\prime })}{2^{{\gamma }_f}(k-{\text{𝒔}}_e(G))}}⩽$$ $${\displaystyle \frac{1}{{\gamma }_f}}{\displaystyle \frac{{\gamma }_{f}v-{\gamma }_{f}v\cdot {\text{𝒔}}_e(G)}{2^{{\gamma }_f}(k-{\text{𝒔}}_e(G))}}={\displaystyle \frac{v}{2^{{\gamma }_f}k}}$$

This completes the proof.

■

Based on the Lemmas 1 and 2, we can analyze the performance of Algorithm 2. In the analysis, Lemma 1 is used for the case $\text{𝒔}(G)=k$ , and Lemma 2 is used for the case $\text{𝒔}(G)<k$ .

Theorem 1 For any $\epsilon \in (0,1)$ and given function $f\in F_{𝒄}$ , Algorithm 2 is a two-pass algorithm, the approximation is $\min \{(1-\epsilon ){\gamma }_f/2^{{\gamma }_f},(1-1/{\gamma }_f^w{2}^{{\gamma }_f})\}$ , the memory complexity is $O(\frac{k}{\epsilon }\log \frac{k}{\epsilon })$ , and the query times per element is $O(\frac{\log k}{\epsilon }\log \frac{\log k}{\epsilon })$ .

Proof Suppose ${\text{𝒔}}^{*}=\underset{e\in \{{\text{𝒔}}^{*}\}}{\sum }{\chi }_e$ . From the definition of the DR ratio, we obtain

$$OPT=f({\text{𝒔}}^{*})=f\left({\displaystyle \underset{e\in \{{\text{𝒔}}^{*}\}}{\sum }}{\chi }_e\right)⩽$$ $$\mathrm{\hspace{1em}}\mathit{\hspace{1em}}{\displaystyle \frac{1}{{\gamma }_f}}{\displaystyle \underset{e\in \{{\text{𝒔}}^{*}\}}{\sum }}f({\chi }_e)⩽{\displaystyle \frac{k\cdot m}{{\gamma }_f}}.$$

Moreover,

(6) $$m=\underset{e\in G}{\max }f({\chi }_e)⩽f({\text{𝒔}}^{*})$$

Combined Formulas (5) and (6), we have

$$m⩽OPT⩽\frac{k\cdot m}{{\gamma }_f}.$$

Let $\bar{i}=\lfloor {\log }_{1+\epsilon }OPT\rfloor$ , thus there exists $v={(1+\epsilon )}^{\bar{i}}$ , such that $v⩽OPT$ and

(7) $$v⩾{\displaystyle \frac{OPT}{1+\epsilon }}⩾\max \{(1-\epsilon )OPT,{\displaystyle \frac{m}{1+\epsilon }}\}$$

From Formulas (6) and (7), we obtain

$$v\in [(1-\epsilon )OPT,OPT].$$

Next, for $v\in V_{\epsilon }$ , we denote ${\text{𝒔}}^v$ as the output of Algorithm 2, and consider the following two cases:

(1) ${\text{𝒔}}^v(G)=k$

According to Lemma 1, we have

(8) $$f({\text{𝒔}}^v)⩾{\displaystyle \frac{{\gamma }_{f}v{\text{𝒔}}^v(G)}{2^{{\gamma }_f}k}}={\displaystyle \frac{(1-\epsilon ){\gamma }_f}{2^{{\gamma }_f}}}OPT$$

(2) ${\text{𝒔}}^v(G)<k$

From Lemma 2 and the weak DR ratio, we have

$$f({\text{𝒔}}^{*}\cup {\text{𝒔}}^v)-f({\text{𝒔}}^v)⩽$$ $${\displaystyle \frac{1}{{\gamma }_f^w}}{\displaystyle \underset{e\in suu{p}^{+}\{{\text{𝒔}}^{*}-{\text{𝒔}}^v\}}{\sum }}f(({\text{𝒔}}^{*}-{\text{𝒔}}^v)(e){\chi }_e|{\text{𝒔}}^v)⩽$$ $${\displaystyle \frac{1}{{\gamma }_f^w}}{\displaystyle \underset{e\in \{{\text{𝒔}}^{*}\}\setminus \{{\text{𝒔}}^v\}}{\sum }}f({\chi }_e|{\text{𝒔}}^v)<$$ $${\displaystyle \frac{1}{{\gamma }_f^w}}{\displaystyle \underset{e\in \{{\text{𝒔}}^{*}\}\setminus \{{\text{𝒔}}^v\}}{\sum }}{\displaystyle \frac{v}{2^{{\gamma }_f}k}}⩽$$ $${\displaystyle \frac{v}{{\gamma }_f^w{2}^{{\gamma }_f}}}⩽{\displaystyle \frac{OPT}{{\gamma }_f^w{2}^{{\gamma }_f}}}.$$

As $f({\text{𝒔}}^{*}\cup {\text{𝒔}}^v)-f({\text{𝒔}}^v)⩾OPT-f({\text{𝒔}}^v)$ , we obtain

(9) $$f({\text{𝒔}}^v)⩾(1-{\displaystyle \frac{1}{{\gamma }_f^w{2}^{{\gamma }_f}}})OPT$$

Combining Formulas (8) and (9), we obtain

$$f({\text{𝒔}}^v)⩾\min \{\frac{(1-\epsilon ){\gamma }_f}{2^{{\gamma }_f}},1-\frac{1}{{\gamma }_f^w{2}^{{\gamma }_f}}\}OPT.$$

From Algorithm 2, we know that $\widetilde{\text{𝒔}}=\arg \underset{v\in V_{\epsilon }}{\max }f({\text{𝒔}}^v)$ . Thus, we can conclude that

$$f(\widetilde{\text{𝒔}})⩾f({\text{𝒔}}^v)⩾\min \{\frac{(1-\epsilon ){\gamma }_f}{2^{{\gamma }_f}},1-\frac{1}{{\gamma }_f^w{2}^{{\gamma }_f}}\}OPT$$

The proof is completed.

■

For the streaming algorithm, the number of rounds to read data is an important index to measure the performance of such an algorithm. Naturally, we want to obtain a one-pass streaming algorithm by dynamically updating the maximum value of the standard unit vector according to the arriving elements and replacing the estimation value range of the OPT at the same time. We design the one-pass streaming algorithm for the NMCC, which is stated in Algorithm 3. Here, ${\gamma }_f$ is unknown at the beginning. However, as $f({\chi }_e)>0$ , we also know ${\gamma }_f>0$ . Thus, there is an expression $\epsilon \in (0,1)$ that satisfies ${\gamma }_f>\epsilon$ .

Theorem 2 For any given $\epsilon \in (0,1)$ and function $f\in F_{𝒄}$ , Algorithm 2 is a one-pass algorithm, the approximation is $\min \{(1-\epsilon ){\gamma }_f/2^{{\gamma }_f},(1-1/{\gamma }_f^w{2}^{{\gamma }_f})\}$ , the memory complexity is $O(\frac{k}{\epsilon }\log \frac{k}{{\epsilon }^2})$ , and the query times per element is $O(\frac{\log k}{\epsilon }\log \frac{k}{{\epsilon }^2})$ .

Proof Similar to the proof of Theorem 1, we can obtain a $v\in V_{\epsilon }^i$ , such that $(1-\epsilon )OPT⩽v⩽OPT$ . Let ${\text{𝒔}}^v$ be the output solution with respect to $v$ . Therefore,

$$f({\text{𝒔}}^v)⩾\min \{(1-\epsilon ){\gamma }_f/2^{{\gamma }_f},(1-1/{\gamma }_f^w{2}^{{\gamma }_f})\}\cdot OPT.$$

As the return vector of Algorithm 3 satisfies

$${\text{𝒔}}^v=\arg \underset{v\in V_{\epsilon }^n}{\max }f({\text{𝒔}}^v),$$

we can conclude that

$$f(\text{𝒔})⩾f({\text{𝒔}}^v)⩾$$ $$\min \{(1-\epsilon ){\gamma }_f/2^{{\gamma }_f},(1-1/{\gamma }_f^w{2}^{{\gamma }_f})\}\cdot OPT.$$

■

Asides from the number of rounds to reading the data, the memory complexity is also an important index to measure the performance of a streaming algorithm. In Algorithm 3, the memory complexity relies on the amount of $v\in V_{\epsilon }^i$ and the cardinality constraint $k$ . Then, we take measures to reduce the lower amount of $v$ in order to reduce memory complexity. The improved one-pass streaming algorithm is presented as following.

Theorem 3 For any given $\epsilon \in (0,1)$ and function $f\in F_{𝒄}$ , Algorithm 4 is a one-pass $\min \{(1-\epsilon ){\gamma }_f/2^{{\gamma }_f},(1-1/{\gamma }_f^w{2}^{{\gamma }_f})\}$ -approximation algorithm for NMCC, with $O(\frac{k}{{\epsilon }^2})$ memory complexity and $O(\frac{\log k}{\epsilon }\log \frac{k}{\epsilon })$ query times per item.

Proof We can obtain the approximation by using the same method as Theorem 2. Thus, we omit the explanation here, and skip to the analysis of the memory complexity of Algorithm 4. On the one hand, after the $(i-1)$ -th iteration we obtain

$$m_i=\underset{l=1,2,\mathrm{\cdots }i}{\max }f({\chi }_{e_i}),$$

and

$${\beta }_i=\underset{l=1,2,\mathrm{\dots }i}{\max }\underset{v^l\in V_{\epsilon }^l}{\max }f(\text{𝒔}_l^{v^l}).$$

Therefore, we have

$${\zeta }_i=\max \{m_i,{\beta }_{i-1}\},$$

and

$$V_{\epsilon }^i=\{{(1+\epsilon )}^q|\frac{{\zeta }_i}{1+\epsilon }⩽{(1+\epsilon )}^q⩽\frac{2k{m}_i}{{\gamma }_f\epsilon }\}.$$

On the other hand, after the $i$ -th iteration we have

$${\beta }_i=\max \{{\beta }_{i-1},\underset{v^i\in V_{\epsilon }^i}{\max }f(\text{𝒔}_i^{v^i})\}.$$

It is easy to check that ${\beta }_{i-1}⩽{\beta }_i$ . Thus, there is no need to save the vector $\text{𝒔}_i^{v^i}$ with $v^i⩽{\beta }_i$ . We need only to consider the vector $\text{𝒔}_i^{v^i}$ corresponding to these $v_p^i\in {\bar{V}}_{\epsilon }^i=\{{(1+\epsilon )}^t|\frac{{\beta }_i}{1+\epsilon }⩽$ ${(1+\epsilon )}^t⩽\frac{2k{m}_i}{{\gamma }_f\epsilon }\}$ . The number of $v_p^i$ in ${\bar{V}}_{\epsilon }^i$ is $\lceil \frac{1}{\epsilon }\log \frac{2k}{{\epsilon }^2}\rceil$ .

From Lemma 1, we obtain

$$\text{𝒔}_i^{v_p^i}(G)⩽\frac{2^{{\gamma }_f}k}{{\gamma }_f{v}_p^i}f(\text{𝒔}_i^{v_p^i})⩽$$ $$\frac{2^{{\gamma }_f}k{\beta }_i}{{\gamma }_f{(1+\epsilon )}^p{\beta }_i}⩽\frac{2^{{\gamma }_f}k}{{\gamma }_f{(1+\epsilon )}^p}.$$

Then, for each iteration, the memory complexity is expressed as follows:

$$\underset{p=0}{\overset{\lceil \frac{1}{\epsilon }\log \frac{2k}{{\epsilon }^2}\rceil }{\sum }}\frac{2^{{\gamma }_f}k}{{\gamma }_f{(1+\epsilon )}^p}⩽\frac{2k}{\epsilon }\underset{p=0}{\overset{\lceil \frac{1}{\epsilon }\log \frac{2k}{{\epsilon }^2}\rceil }{\sum }}\frac{1}{{(1+\epsilon )}^p}=O\left(\frac{k}{{\epsilon }^2}\right).$$

For any $e\in G$ , the number of $v$ is at most $O(\frac{1}{\epsilon }\log \frac{k}{{\epsilon }^2})$ . Meanwhile, for each $e\in G$ and per $v$ , the query time is $O(\log k)$ . Thus, for each item, the update time is $O(\frac{\log k}{\epsilon }\log \frac{k}{{\epsilon }^2})$ .

■