## 1 Introduction  
Online social networks (OSNs) have recently been a very effective method for diffusing information, propagating opinions or ideas. Many companies have leveraged word-of-mouth effect in OSNs to promote their products. The key problem of viral marketing is Influence Maximization (IM), which aims to select a set of \(k\) users (called _seed set_) in a social network with maximum influence spread. [PERSON] et al. [1] first formulated IM problem in two diffusion models, named Linear Threshold (LT) and Independent Cascade (IC), which simulate the propagation of influence through social networks. IM has been widely studied due to its important role in viral marketing [2; 3; 4; 5; 6; 7; 8; 9; 10]. However, all of the above-mentioned studies only focus on studying influence propagation of single player or company in social networks. In the context of viral marketing, there are often many competitors simultaneously implementing the same strategy of marketing spread on OSNs. This phenomenon requires the task of maximizing a product's influences under competitive circumstances, called Competitive Influence Maximization (CIM) problem. [PERSON] et al. [11] first proposed CIM problem, which seeks a seed set to maximize the propagation of their product's information while their competitors employ the same strategy. Since then, related works have tried to investigate CIM in many different contexts. Some authors show that the objective function is _monotone_ and _submodular_. A set function \(f\) over a ground \(U\) is set to be submodular if  
\[f(A\cup\{u\})-f(A)\geq f(B\cup\{u\})-f(B) \tag{1}\]  
for any \(A\subseteq B\subseteq U,u\in U\setminus B\). Based on that, they applied the classic hill-climbing algorithm, which provides a napproximation ratio of \((1-1/e)\) to solve CIM problem [12; 13; 14; 15; 16; 17]. For example, [PERSON] et al. [12] studied the problem in context of fair competitive influence from the host perspective. [PERSON] et al. [13] proposed an independent cascade model with negative opinions (IC-N) model by extending IC model and showed a greedy algorithm with the approximation ratio of \(1-1/e\). Recently, some works have addressed the problem in other directions, including proposing heuristic algorithm [15] and studying some variants of CIM [16; 18; 19]. Although previous works try to solve the CIM problem in many circumstances, the feasibility of the existing works is limited for following reasons. Firstly, they often assume that one of the competitors takes advantage of the competitive influence process. In this case, the objective function is monotone and submodular. As a result, the existing algorithms provide an approximation ratio of \(1-1/e\) based on using Greedy framework algorithm, which sequentially selects the node that has the largest marginal benefit [20]. However, users also have different views when they receive the same information. As a result, the influence function is no longer submodular and there is no approximation algorithm for this case. Secondly, the prior works do not take into account time constraint and cost to select a seed user for CIM. In a more realistic scenario, the effectiveness of competitive influence process depends very much on these two factors. Thirdly, although many CIM algorithms have been proposed, there are no scalable and efficient algorithms for CIM in large social networks (million-scale). For the problems related to information diffusion, the complexity of calculating the objective function is enormous due to the randomness of the probabilistic diffusion model [8; 9]. To address these challenges, some works use Note-Carlo method to estimate the objective function [1; 13; 15; 17]. However, the method requires high complexity, and it takes several hours even on very small networks. To the best of our knowledge, there is no randomized algorithm for CIM that can meet approximation guarantee with low complexity.