## 5 Our Proposed Algorithm for BCIM Problem
### Polling-Based Algorithm for Maximum Bound Functions
Last, we return \(S_{sa}=\arg\max_{S\in\{S_{L},S^{\prime},S_{U}\}}\mathbb{I}(S)\) as the solution of SPBA algorithm. The details of our algorithm are shown in Algorithm 7. ```
Input: Graph \(G=(V,E,w_{A},w_{B})\), budget \(L>0\), and \(\epsilon,\delta,\epsilon^{\prime},\delta^{\prime}\in(0,1)\) Output: Seed set \(S_{A}\)
1.\(S_{U}\leftarrow\mathsf{PBA}(\mathbb{L},G,L,\epsilon,\delta)\)
2.\(S_{L}\leftarrow\mathsf{PBA}(\mathbb{U},G,L,\epsilon,\delta)\)
3.\(S^{\prime}\leftarrow\) a solution for maximizing \(\mathbb{I}\) by any algorithm. 4.\(S\leftarrow\arg\max_{S\in\{S_{U},S_{L}S^{\prime}\}}\mathbb{I}(S)\)
5.return\(S\);
```

**Algorithm 7**Sandwich Approximation base on PBA algorithm (SPBA). The following theorem shows the approximation ratio of our algorithm. Theorem 6: _Let \(S^{*}\) be the optimal solution, and \(S_{sa}\) be a solution returned by Algorithm 7. We have:_

\[\mathbb{I}(S_{sa})\geq\max\left\{\frac{\mathbb{I}(S_{U})}{\mathbb{U}(S_{U})}, \frac{\mathbb{L}(S^{*}_{L})}{\mathbb{I}(S^{*}_{A})}\right\}\frac{(1-\epsilon^{ \prime})}{(1+\epsilon^{\prime})}\left(1-\frac{1}{\sqrt{\epsilon}}-\epsilon \right)\mathsf{OPT} \tag{35}\]

_with probability at least \(1-2\delta-\delta^{\prime}\)._

Proof: Due to \(\mathbb{U}(S^{*}_{U})\geq\mathbb{U}(S^{*}_{A})\geq\mathbb{I}(S^{*}_{A})\), we have:

\[ \begin{array}{ll}\mathbb{I}(S_{U})&=\frac{\mathbb{I}(S_{U})}{\mathbb{U}(S_{ U})}\mathbb{U}(S_{U})\geq\frac{\mathbb{I}(S_{U})}{\mathbb{U}(S_{U})}\left(1- \frac{1}{\sqrt{\epsilon}}-\epsilon\right)\mathbb{U}(S^{*}_{U})\\ &\geq\frac{\mathbb{I}(S_{U})}{\mathbb{U}(S_{U})}(1-\epsilon^{\prime})\left(1- \frac{1}{\sqrt{\epsilon}}-\epsilon\right)\mathbb{I}(S^{*}_{A})\end{array}  \tag{36}\]

On the other hand,

\[ \begin{array}{ll}\mathbb{I}(S_{L})&\geq(1-\epsilon^{\prime})\mathbb{I}(S_{L })\geq(1-\epsilon^{\prime})\mathbb{L}(S_{L})\\ &\geq\left(1-\frac{1}{\sqrt{\epsilon}}-\epsilon\right)\mathbb{L}(S^{*}_{L})\\ &\geq\frac{\mathbb{I}(S^{*}_{L})}{\mathbb{I}(S^{*}_{A})}(1-\epsilon^{\prime}) \left(1-\frac{1}{\sqrt{\epsilon}}-\epsilon\right)\mathbb{I}(S^{*}_{A})\end{array}  \tag{37}\]

Since \((1-\epsilon^{\prime})\mathbb{I}(S_{sa})\leq\mathbb{I}(S_{sa})\leq(1+\epsilon^ {\prime})\mathbb{I}(S_{sa})\), we have:

\[\mathbb{I}(S_{sa})\geq\frac{1}{1+\epsilon^{\prime}}\mathbb{I}(S_{sa})\geq\max \left\{\frac{\mathbb{I}(S_{U})}{\mathbb{U}(S_{U})},\frac{\mathbb{L}(S^{*}_{L} )}{\mathbb{I}(S^{*}_{A})}\right\}\cdot\frac{(1-\epsilon^{\prime})}{(1+\epsilon ^{\prime})}(1-\frac{1}{\sqrt{\epsilon}}-\epsilon)\cdot\mathsf{OPT}_{u}\]

Applying union bound of probabilities, the inequality in Equation (38) happens with probability at least \(1-2\delta-\delta^{\prime}\). ## 6 Experiments

We experimentally evaluated and compared the performance of our algorithm to other algorithms, namely baseline algorithms and influence maximization methods, on two aspects: solution quality and the scalability from various network datasets. ### Experimental Settings

#### 6.1.1 Datasets

We performed our experiments on six real-world datasets: Gnutella, Enron, Epinions, Email-Eu, DBLP and Wiki.The basic statistics of these networks are summarized in Table 2.

#### 6.1.2 Algorithm Compared

We compared our algorithm with influence maximization BCT algorithm and several baseline algorithms, which are described as follows \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Dataset** & **Nodes** & **Edges** & **Type** & **Avg. Degree** \\ \hline Gnutella [36] & 6301 & 20,777 & Directed & 3.29 \\ Enron [37] & 36,692 & 183,831 & Undirected & 5.01 \\ Epinions [38] & 75,879 & 508,837 & Directed & 6.7 \\ Email-Eu [36] & 265,214 & 420,045 & Directed & 1.58 \\ DBLP [39] & 317,080 & 1,049,866 & Undirected & 5.01 \\ Wiki [40] & 1,791,489 & 28,511,807 & Directed & 6.7 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Datasets. * BCT: An influence maximization algorithm under the heterogeneous selecting cost. The reason we chose BCT to compare is that BCIM is a variant of IM and BCT considers of nodes with arbitrary costs.