## 5 Our Proposed Algorithm for BCIM Problem
### Polling-Based Algorithm for Maximum Bound Functions
```
Input:\(\mathcal{R}_{t},\mathsf{Cov}_{\mathcal{R}_{t}}(S_{A}),\delta,\epsilon\) Output: True or (False and \(\mathcal{R}_{t+1}\))
1.\(\delta_{1}=\frac{\delta}{3l_{max}},\epsilon_{1}=\epsilon\),
2.\(cov\leftarrow\mathsf{Cov}_{\mathcal{R}_{t}}(S_{A})\)
3.\(\mathcal{R}_{c}\leftarrow\mathcal{R}_{t}\)
4.for\(i=1\)to\(|\mathcal{R}_{t}|\)do
5 Generate a URR set \(R_{j}\) by Algorithm 4 and add it to \(\mathcal{R}_{c}\)
6 If \(R_{j}\cap S_{A}\
eq 0\), then \(cov\gets cov+1\)
7. end for
8.\(a\leftarrow\frac{cov-1}{\ln(2\delta_{1}^{-1})}\)
9. If \(a=\frac{2}{3}\)return False and \(\mathcal{R}_{c}\)
10.\(\epsilon_{1}^{1}\leftarrow\frac{1}{a-\frac{2}{3}}\left(\frac{4}{3}-\sqrt{2a+ \frac{4}{9}}\right)\), \(\epsilon_{1}^{2}\leftarrow\frac{1}{a-\frac{2}{3}}\left(\frac{4}{3}+\sqrt{2a+ \frac{4}{9}}\right)\)
11.\(\epsilon_{1}\leftarrow\min\{\epsilon^{\prime}\in\{\epsilon_{1}^{1},\epsilon_{ 2}^{1}\}|\epsilon^{\prime}>0\}\)
12.\(\epsilon_{2}\leftarrow\sqrt{\frac{2(1+\epsilon_{1})|\mathcal{R}_{c}|\ln\frac {3l_{max}}{\epsilon_{1}}}{|\mathcal{R}_{t}|\cup\epsilon_{c}}(S)}\)
13.\(f_{l}(S_{A},\mathcal{R}_{c},\epsilon_{1})\leftarrow\frac{n_{0}}{(1+\epsilon _{1})|\mathcal{R}_{c}|}\mathsf{Cov}_{\mathcal{R}_{c}}(S_{A})\)
14.\(f_{u}(S_{A},\mathcal{R}_{t},\epsilon_{2})\leftarrow\frac{n_{0}\mathsf{Cov}_ {\mathcal{R}_{t}}(S_{A})}{|\mathcal{R}_{t}|(1-\sqrt{e})(1-\epsilon_{2})}\)
15.if\(\frac{f_{l}(S_{A})}{f_{u}(\mathsf{OPT}_{u})}\geq 1-\frac{1}{\sqrt{e}}-\epsilon\)then
16. return True
17.else
18. return False and \(\mathcal{R}_{c}\)
19. end for
20.return False;
```
**Algorithm 6**Check quality of solution (CheckQS). #### 5.2.2 Theoretical Analysis

Now, we prove that PBA returns a \((1-1/\sqrt{e}-\epsilon)\)-approximation solution with probability at least \(1-\delta\). We observe that \(X_{j}\in[0,1]\). Let random variable \(Z_{i}=\sum_{j=1}^{i}(X_{j}-\mathbb{E}[X_{j}]),\forall i\geq 1\). For a sequence random variables \(Z_{1},Z_{2},\ldots\), we have \(\mathbb{E}[Z_{i}|Z_{1},\ldots,Z_{j-1}]=E[Z_{i-1}]+\mathbb{E}[X_{i}-\mu_{X}]= \mathbb{E}[Z_{i-1}]\). Hence, \(Z_{1},Z_{2},\ldots\) is a form of martingale [34]. Therefore, we obtain the same results as in [6]. **Lemma 5** ([6]): _For any \(T>0,\epsilon>0\), \(\mu\) is the mean of \(X_{j}\), and an estimation of \(\mu\) is \(\hat{\mu}=\frac{\sum_{i=1}^{T}X_{i}}{T}\). We have:_

\[\Pr[\hat{\mu}\geq(1+\epsilon)\mu] \leq\exp\left(\frac{-T\mu\epsilon^{2}}{2+\frac{2}{3}\epsilon}\right) \tag{22}\] \[\Pr[\hat{\mu}\leq(1-\epsilon)\mu] \leq\exp\left(\frac{-T\mu\epsilon^{2}}{2}\right) \tag{23}\]

Based on Lemma 5, [PERSON] et al. [6] proposed IMM algorithm based on _Reverse Influence Set (RIS)_[24] process for solving IM problem. They showed that the number of random _Reachable Reversal (RR)_ sets, which ensures RIS process returns an \((1-1/e)\)-approximation with probability \(1-\delta\), is

\[\theta_{max}=2n\left(\left(1-\frac{1}{e}\right)\sqrt{\ln(\frac{2}{\delta})}+ \sqrt{\left(1-\frac{1}{e}\right)\left(\ln\frac{2}{\delta}+\ln\binom{n}{k} \right)}\right)^{2}\frac{1}{\epsilon^{2}k} \tag{24}\]

This threshold is also used to obtain stopping condition for IM algorithms [4; 7]. However, it does not guarantee that the candidate solution \(S_{A}\) is a \((1-1/\sqrt{e})\)-approximation under the heterogeneous selecting costs. In this case, we provide the number of URR sets to guarantee \((1-1/\sqrt{e})\)-approximation ratio by the following theorem.