## 5 Our Proposed Algorithm for BCIM Problem
### Polling-Based Algorithm for Maximum Bound Functions
**Theorem 4**: _For \(\epsilon>0\), \(\delta\in(0,1)\) is the parameter.If \(|\mathcal{R}|\) is greater or equal to_

\[N(\epsilon,\delta)=2n_{0}\left((1-\frac{1}{\sqrt{e}})\sqrt{\ln(\frac{2}{\delta })}+\sqrt{\left(1-\frac{1}{\sqrt{e}}\right)\left(\ln\frac{2}{\delta}+\ln \binom{n}{kmax}\right)}\right)^{2}\frac{1}{\epsilon^{2}\mathsf{OPT}_{u}}\]

_Algorithm 5 returns a \((1-1/\sqrt{e}-\epsilon)\)-approximation solution with probability at least \(1-\delta\)._

**Lemma 6**: _Let event \(B_{t}^{1}=\left(|\mathcal{R}_{t}|\geq N_{max}\right)\bigwedge\left(\mathbb{U}( S)<(1-1/\sqrt{e}-\epsilon)\mathsf{OPT}_{u})\right)\) then, \(\Pr[B_{t}^{1}]<\frac{\delta}{3}\)._

From Theorem 4, since \(N_{max}\geq N\left(\epsilon,\frac{\delta}{3}\right)\), the bad event \(\mathbb{U}(S)<(1-1/\sqrt{e}-\epsilon)\mathsf{OPT}_{u}\) happens with probability at most \(\frac{\delta}{3}\)

**Lemma 7**: _For each \(1\leq t\leq t_{max}\), let \(f_{l}(S_{A},\mathcal{R}_{c},\epsilon_{1})=\frac{n_{0}}{|\mathcal{R}_{c}|(1+ \epsilon_{1})}\mathsf{Cov}_{\mathcal{R}_{c}}(S_{A})\). We have: \(\Pr[f_{l}(S_{A},\mathcal{R}_{c},\epsilon_{1})\leq\mathbb{U}(S_{A})]\geq 1-\delta_ {1}\)_

We denote \(\mathbb{U}_{c}(S_{A})\) as an estimation of \(\mathbb{U}(S_{A})\) over \(\mathcal{R}_{c}\). In each iterator \(t\), after ending the for loop (Line 7) in Algorithm 6, we have

\[\mathsf{Cov}_{\mathcal{R}_{c}}(S_{A})=\mathrm{Y}(\epsilon_{1},\delta_{1})=(1+ \epsilon_{1})\left(2+\frac{2}{3}\epsilon_{1}\right)\ln\frac{2}{\delta_{1}} \frac{1}{\epsilon_{1}^{2}}\]

It satisfies the stopping rule theorem in [35], therefore it guarantees that

\[\Pr[\mathbb{U}_{c}(S_{A})\leq(1+\epsilon_{1})\mathbb{U}(S_{A})]=\Pr[\hat{ \mu}_{c}\leq(1+\epsilon_{1})\mu]\geq 1-\delta_{1}\]

Hence, \(\Pr[f_{l}(S_{A})\leq\mathbb{U}(S_{A})]\geq 1-\delta_{1}\)

**Lemma 8**: _Assume that the bad event in Lemma 7 does not happen. Let \(f_{u}(S_{A},\mathcal{R}_{t},\epsilon_{2})=\frac{n_{0}\mathsf{Cov}_{\mathcal{R}_ {t}}(S_{A})}{|\mathcal{R}_{t}|(1-\sqrt{e})(1-\epsilon_{2})}\). We have: \(\Pr[f_{u}(S_{A},\mathcal{R}_{t},\epsilon_{2})\geq\mathbb{U}(S_{t}^{*})]\geq 1- \delta_{1}\)._Proof. : Since the bad event in Lemma 7 does not happen, we have \(\mu(S_{A})(1+\epsilon_{1})\geq\hat{\mu}_{c}(S_{A})\). Applying Lemma 5 for optimal set \(S_{U}^{*}\), with random variable \(X_{j}\), the mean \(\mu(S_{U}^{*})=\mathbb{U}(S_{U}^{*})/n_{0}\), and \(|\mathcal{R}_{t}|\) samples

\[\Pr[\hat{\mathbb{U}}_{t}(S_{U}^{*})<(1-\epsilon_{2})\mathbb{U}(S _{U}^{*})] =\Pr[\hat{\mu}_{t}(S_{U}^{*})<(1-\epsilon_{2})\mu(S_{U}^{*})]\] \[\leq\exp\left(-\frac{|\mathcal{R}_{t}|\epsilon_{2}^{2}\mu(S_{U}^{ *})}{2}\right)\leq\exp\left(-\frac{|\mathcal{R}_{t}|\epsilon_{2}^{2}\mu(S_{A} )}{2}\right)\] \[\frac{f_{l}(S_{A},\mathcal{R}_{c},\epsilon_{1})}{f_{u}(\mathsf{OPT }_{u},\mathcal{R}_{t},\epsilon_{2})}\geq 1-\frac{1}{\sqrt{e}}-\epsilon \tag{21}\]0

Now, since Greedy algorithm returns a \((1-1/\sqrt{e})\)-approximation solution, we have:

\[\frac{f_{l}(S_{A},\mathcal{R}_{c},\epsilon_{1})}{f_{u}(\mathsf{OPT }_{u},\mathcal{R}_{t},\epsilon_{2})}\geq 1-\frac{1}{\sqrt{e}}-\epsilon \tag{21}\]1 \[\frac{f_{l}(S_{A},\mathcal{R}_{c},\epsilon_{1})}{f_{u}(\mathsf{OPT }_{u},\mathcal{R}_{t},\epsilon_{2})}\geq 1-\frac{1}{\sqrt{e}}-\epsilon \tag{21}\]2 \[\frac{f_{l}(S_{A},\mathcal{R}_{c},\epsilon_{1})}{f_{u}(\mathsf{OPT }_{u},\mathcal{R}_{t},\epsilon_{2})}\geq 1-\frac{1}{\sqrt{e}}-\epsilon \tag{21}\]3

where \(S_{t}^{*}\) is an optimal solution of instance \((\mathcal{R}_{t},L)\) of maximum coverage problem. Therefore, \(f_{u}(S_{A},\mathcal{R}_{t},\epsilon_{2})=\frac{\hat{\mathbb{U}}(S)}{(1-1/ \sqrt{e})(1-\epsilon_{2})}\geq\mathbb{U}(S_{U}^{*})\) with probability at least \(1-\delta_{1}\). **Theorem 5**. : _Given \(0\leq\epsilon,\delta\leq 1\), PBA algorithm returns the set node \(S\) satisfying:_

\[\frac{f_{l}(S_{A},\mathcal{R}_{c},\epsilon_{1})}{f_{u}(\mathsf{OPT }_{u},\mathcal{R}_{t},\epsilon_{2})}\geq 1-\frac{1}{\sqrt{e}}-\epsilon \tag{21}\]4

Proof. : Assume that none of the bad events in Lemmas 6-8 happen in any iterator \(t=1,2\ldots,t_{max}\).