## 5 Our Proposed Algorithm for BCIM Problem
### Polling-Based Algorithm for Maximum Bound Functions
By setting \(\theta_{1}=\theta_{2}=\theta/2,\epsilon_{2}=\epsilon-(1-1/\sqrt{e})\epsilon_ {1}\), and

\[\epsilon_{1}=\frac{\epsilon\sqrt{\ln(2/\delta)}}{(1-1/\sqrt{e})\sqrt{\ln(2/ \delta)}+\sqrt{(1-1/\sqrt{e})\ln\left(2\binom{n_{0}}{k_{max}}/\delta\right)}}\]

we obtain \(\theta_{1}=\theta_{2}=N(\delta,\epsilon)\). Hence, if \(T\geq N(\delta,\epsilon)\), Algorithm 5 returns a \((1-1/\sqrt{e}-\epsilon)\)-approximation solution with probability at least \(1-(\delta_{1}+\delta_{2})=1-\delta\). ## References

* [PERSON] et al. (2003) [PERSON]; [PERSON]; [PERSON] Maximizing the spread of influence through a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, 24-27 August 2003; pp. 137-146. [CrossRef]
* [PERSON] et al. (2014) [PERSON]; [PERSON]; [PERSON]; [PERSON] Maximizing Social Influence in Nearly Optimal Time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, ON, USA, 5-7 January 2014; pp. 946-957. [CrossRef]
* [PERSON] et al. (2007) [PERSON]; [PERSON]; [PERSON]; [PERSON] [PERSON]; [PERSON] [PERSON]; Glance, N.S. Cost-effective outbreak detection in networks. In Proceedings of the 13 th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, CA, USA, 12-15 August 2007; pp. 420-429. [CrossRef]
* [PERSON] and [PERSON] (2016) [PERSON]; [PERSON]; [PERSON] Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, 26 June-1 July 2016; pp. 695-710. [CrossRef]
* [PERSON] et al. (2014) [PERSON]; [PERSON]; [PERSON] Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the International Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA, 22-27 June 2014; pp. 75-86. [CrossRef]
* [PERSON] et al. (2015) [PERSON]; [PERSON]; [PERSON] Influence Maximization in Near-Linear Time: A Martingale Approach. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, 31 May-4 June 2015; pp. 1539-1554. [CrossRef]
* [PERSON] et al. (2017) [PERSON]; [PERSON]; [PERSON] A Billion-Scale Approximation Algorithm for Maximizing Benefit in Viral Marketing. _IEEE/ACM Trans. Netw._**2017**, _25_, 2419-2429. [CrossRef]
* [PERSON] et al. (2010) [PERSON]; [PERSON]; [PERSON] Scalable Influence Maximization in Social Networks under the Linear Threshold Model. In Proceedings of the 10 th IEEE International Conference on Data Mining, Sydney, Australia, 14-17 December 2010; pp. 88-97. [CrossRef]
* [PERSON] et al. (2010) [PERSON]; [PERSON]; [PERSON] Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16 th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, 25-28 July 2010; pp. 1029-1038. [CrossRef]
* [PERSON] and [PERSON] (2013) [PERSON]; [PERSON] On Budgeted Influence Maximization in Social Networks. _IEEE J. Sel. Areas Commun._**2013**, _31_, 1084-1094. [CrossRef]
* [PERSON] et al. (2007) [PERSON]; [PERSON]; [PERSON] Competitive Influence Maximization in Social Networks. In Proceedings of the Internet and Network Economics, Third International Workshop, WINE 2007, San Diego, CA, USA, 12-14 December 2007; pp. 306-311. [CrossRef]
* [PERSON] et al. (2013) [PERSON]; [PERSON]; [PERSON]; [PERSON]. The bang for the buck: Fair competitive viral marketing from the host perspective. In Proceedings of the 19 th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013, Chicago, IL, USA, 11-14 August 2013; pp. 928-936. [CrossRef]
* [PERSON] et al. (2011) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate.