## 5 Our Proposed Algorithm for BCIM Problem
### Polling-Based Algorithm for Maximum Bound Functions
```
Input: Graph \(G=(V,E,w_{A},w_{B})\), budget \(L>0\), and \(\epsilon,\delta\in(0,1)\) Output:\(A\)-seed set \(S_{A}\)
1.\(\Lambda=N_{max}\cdot k_{max}\epsilon^{2}/n\), \(t\gets 1\), \(N_{max}\gets N(\epsilon,\frac{\delta}{3})\frac{\text{OPT}_{T}}{k_{max}}\), \(t_{max}=\Big{\lceil}\log_{2}\frac{N_{max}}{\Lambda}\Big{\rceil}\)
2 Generate \(\Lambda\) URR sets by Algorithm 4 and add them into \(\mathcal{R}_{1}\)
3 repeat
4\(<S_{A},\text{Cov}_{\mathcal{R}_{t}}(S_{A})>\leftarrow\) Greedy\((\mathcal{R}_{t},L)\)
5 ifCheckQS\((\mathcal{R}_{t},\text{Cov}_{\mathcal{R}_{t}}(S_{A}),\delta,\epsilon)=\) True or \(|\mathcal{R}_{t}|\geq N_{max}\)then
6 return\(S_{A}\)
7 else
8\(t\gets t+1\)
9\(\mathcal{R}_{t}\leftarrow\) CheckQS\((\mathcal{R}_{t},\text{Cov}_{\mathcal{R}_{t}}
```
Input: Graph \(G=(V,E,w_{A},w_{B})\), \(B\)-seed set \(S_{B}\subseteq V\), \(\tau\) Output: a URR set \(R_{j}\)
1 Select randomly a node \(v\in V\setminus S_{B}\)
2\(R_{j}\gets v\); \(d_{A}\gets 0\)
3 while\(d_{A}\leq\tau\)do
4 Select an \(A\)-edge \((u,v)\) by using Competitive live-edge model
5 ifAn edge \((u,v)\) is selectedthen
6\(v\gets u\); \(d_{A}\gets d_{A}+1\)
7 If (\(v\in R_{j}\) or \(v\in S_{B}\)) then break
8 Add \(v\) into \(R_{j}\)
9 else
10 break
11 end if
12
13 end if
14
15 end for
16 return\(R_{j}\);
```
**Algorithm 4**Generate URR set. #### 5.2.1 Description of PBA

PBA first generates a collection \(\mathcal{R}_{1}\) of \(\Lambda\) URR sets. The main phrase of PBA contains several iterators (at most \(t_{max}\)). In each iterator, the algorithm first finds the candidate solution \(S_{A}\) by using Greedy algorithm (Algorithm 5) to solve Budgeted Maximum Coverage (BMC) problem [20] (Line 6). It provides an approximation ratio of \((1-\frac{1}{\sqrt{\epsilon}})\). We denote \(\mathsf{Greedy}(\mathcal{R},L)\) as \(\mathsf{Greedy}\) algorithm with the input data consisting a collection URR sets \(\mathcal{R}\) and budget \(L>0\). Then, \(S_{A}\) is checked for quality in Algorithm 6, which independently generates more \(|\mathcal{R}_{t}|\) URR, adds them to \(\mathcal{R}_{c}\), calculates

\[\mathsf{Cov}_{\mathcal{R}_{c}}(S_{A})=\sum_{R_{j}\in\mathcal{R}_{c}}\min\{|S_{A }\cap R_{j}|,1\} \tag{20}\]
```
Input: URR set \(\mathcal{R}\), budget \(k\) Output: Seed set \(S_{A}\)
1\(S\leftarrow\emptyset\)
2\(U\leftarrow\bigcup_{R_{j}\in\mathcal{R}}R_{j}\)
3 repeat
4\(v\leftarrow\arg\max_{u\in U\setminus S}\big{(}\mathsf{Cov}_{\mathcal{R}}(S \cup\{u\})-\mathsf{Cov}_{\mathcal{R}(S)}\big{)}/c(u)\)
5 if\(c(S\cup\{u\})\leq L\)then
6\(S\gets S\cup\{u\}\)
7 end if
8\(U\gets U\setminus u\)
9 until\(U=\emptyset\);
10\(v_{max}\leftarrow\arg\max_{u\in U\mid c(u)\leq L}\mathsf{Cov}_{\mathcal{R}}(u)\)
11\(S_{1}\leftarrow\arg\max_{S^{\prime}\in\{S,v_{max}\}}\mathsf{Cov}_{\mathcal{R}}(S ^{\prime})\)
12 return\(S_{1}\);
```
**Algorithm 5**Greedy algorithm for Budgeted Maximum Coverage problem--\(\mathsf{Greedy}(\mathcal{R},L)\). and uses it to calculate parameters \(\epsilon_{1},\epsilon_{2}\). We next calculate the lower-bound of \(\mathbb{I}(S_{A})\): \(f_{l}(S,\mathcal{R}_{c},\epsilon_{1})\), and upper-bound of optimal solution \(f_{u}(\mathsf{OPT}_{u},\mathcal{R}_{t},\epsilon_{2})\). If current solution \(S_{A}\) meets approximation guarantee condition that

\[\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}\]

the algorithm returns \(S_{A}\). If not, it moves to the next iterator and stops when the number of URR sets is at least \(N_{max}\).