## 5 Our Proposed Algorithm for BCIM Problem
### Polling-Based Algorithm for Maximum Bound Functions
We have

\[w(u,v)=\frac{1}{|N_{-}(v)|} \tag{38}\]0

According to CLE model, the probability \(v\) is \(A\)-activated in this case is \(P_{2,t}^{\prime}(v)\cdot p_{A}(v|A_{t-1}^{\prime},B_{t-1}^{\prime})\). Thus, the probability \(v\) is \(A\)-activated at step \(t+1\) is

\[w(u,v)=\frac{1}{|N_{-}(v)|} \tag{38}\]1

Due to \(A_{0}=A_{0}^{\prime}=A\), by step-by-step induction, we reach the conclusion that the random CLE model producing the same distribution over \(A\)-active sets as the TCLT model at any hop \(t=0,1,\ldots,\tau\). Similarly, we obtain two models produce the same distribution over \(B\)-active sets. Proof of Theorem 4.: We first show that, for any parameters \(\epsilon_{1}>0\) and \(\theta_{1}\in(0,1)\): If

\[w(u,v)=\frac{1}{|N_{-}(v)|} \tag{38}\]2

then

\[w(u,v)=\frac{1}{|N_{-}(v)|} \tag{38}\]3

with probability at least \(1-\delta_{1}\). Indeed, applying Lemma 5, we obtain

\[ \begin{array}{rl}\Pr[\hat{\mathbb{U}}(S_{U}^{*})\leq(1-\epsilon_{1})\mathbb{U }(S_{U}^{*})]&=\Pr\Big{[}\frac{n_{0}}{T}\sum_{j=1}^{T}X_{j}\leq(1-\epsilon_{1} )\mu\cdot n_{0}\Big{]}\\ &=\Pr\big{[}\hat{\mu}\leq(1-\epsilon_{1})\mu\big{]}\leq\exp\left(-\frac{ \epsilon_{1}^{2}\mu T}{2}\right)=\delta_{1}\end{array}  \tag{19}\]For the instance \((\mathcal{R},L)\), we denote \(S\) as solution Greedy, and \(S_{0}^{*}\) as an optimal solution. Since Algorithm 5 returns a \((1-1/\sqrt{e})\)-approximation solution, the following event happens with probability at least \(1-\delta_{1}\):

\[\hat{\mathbb{U}}(S)\geq(1-1/\sqrt{e})\hat{\mathbb{U}}(S_{0}^{*})\geq(1-1/ \sqrt{e})\hat{\mathbb{U}}(S_{U}^{*})\geq(1-1/\sqrt{e})(1-\epsilon_{1})\hat{ \mathbb{U}}(S_{U}^{*}) \tag{10}\]

We next show that for \(\epsilon_{2}>0,\epsilon_{2}=\epsilon-(1-1/\sqrt{e})\epsilon_{1}\) and \(\delta_{2}\in(0,1)\). If Equation (8) holds, and

\[T\geq\theta_{2}=\frac{2(1-1/\sqrt{e})\ln(\binom{n_{0}}{k_{max}}/\delta_{2})}{ \mathsf{OPT}_{l}(\epsilon-\epsilon_{1}(1-1/\sqrt{e}))^{2}} \tag{11}\]

the following inequality holds with probability at least \(1-\delta_{2}\)

\[\hat{\mathbb{U}}(S)\geq(1-1/\sqrt{e}-\epsilon)\cdot\mathsf{OPT}_{l} \tag{12}\]

Since Equation (8) holds, we have

\[\hat{\mathbb{U}}(S)\geq(1-1/\sqrt{e})(1-\epsilon_{1})\mathbb{U}(S_{U}^{*})=(1- 1/\sqrt{e}-\epsilon)\mathsf{OPT}_{u}+\epsilon_{2}\mathsf{OPT}_{u} \tag{13}\]

Applying Equation (13) and combining with Lemma 5, we have:

\[ \begin{array}{ll}\Pr[\mathbb{U}(S)\leq(1-1/\sqrt{e}-\epsilon)\cdot\mathsf{OPT }_{u}]&\leq\Pr[\hat{\mathbb{U}}(S)-\mathbb{U}(S)\geq\epsilon_{2}\cdot\mathsf{ OPT}_{u}]\\ &=\Pr\left[\frac{n_{0}}{T}\sum_{i=1}^{T}Y_{i}-n_{0}\mu\geq\epsilon_{2}\cdot \mathsf{OPT}_{u}\right]\\ &=\Pr\left[\frac{1}{T}\sum_{i=1}^{T}Y_{i}-\mu\geq\left(\frac{\mathsf{OPT}_{u} \epsilon_{2}}{n_{0}\mu}\right)\cdot\mu\right]\\ &=\Pr\left[\hat{\mu}-\mu\geq\left(\frac{\mathsf{OPT}_{u}\epsilon_{2}}{n_{0} \mu}\right)\cdot\mu\right]\\ &\leq\exp\left(-\frac{\left(\frac{\mathsf{OPT}_{u}\epsilon_{2}}{n_{0}\mu} \right)^{2}T_{u}}{2+3\cdot\left(\frac{\mathsf{OPT}_{u}\epsilon_{2}}{n_{0}\mu} \right)}\right)\\ &\leq\exp\left(-\frac{\epsilon_{2}^{2}\cdot\mathsf{OPT}_{u}^{2}}{2n_{0}^{2} \mu+\frac{1}{5}\epsilon_{2}n_{0}\mathsf{OPT}_{u}}\cdot T\right)\\ &\leq\exp\left(-\frac{\epsilon_{2}^{2}\cdot\mathsf{OPT}_{u}^{2}}{2n_{0}(1-1/ \sqrt{e}-\epsilon)\cdot\mathsf{OPT}_{u}+\frac{1}{5}\epsilon_{2}n_{0}\mathsf{ OPT}_{u}}\cdot T\right)\\ &\leq\exp\left(-\frac{(\epsilon-(1-1/\sqrt{e})\epsilon_{1})^{2}\cdot\mathsf{ OPT}_{u}}{2n_{0}(1-1/\sqrt{e})}\cdot\theta_{2}\right)=\delta_{2}/\binom{n_{0}}{k_{max}} \end{array}  \tag{14}\]

Due to \(k_{max}=\max\{k:\exists S\subseteq V,c(S)\leq L\}\), there are at most \(\binom{n_{0}}{k_{max}}\) candidate solutions. By applying union bound, the inequality in Equation (12) happens with probability at least \(1-\delta_{2}\). From the above results, we found that, if \(T\geq\max\{\theta_{1},\theta_{2}\}\), Algorithm 5 returns a \((1-1/\sqrt{e})\)-approximation solution with probability at least \(1-(\delta_{1}+\delta_{2})\).