## 2 Related Work
### Competitive Influence Maximization  
In the context of viral marketing, it is often the case that many companies propagate their product's information simultaneously, leading to the fact that the Competitive Influence Maximization (CIM) problem has been studied in recent years. [PERSON] et al. [11] first proposed CIM problem by proposing a new propagation model, which is an extension of IC model. Later, some authors proposed variations of the IC model for CIM problem. [PERSON] et al. [13] investigated CIM under the context of combating the dissemination of negative opinions under IC-N model. This model is based on the observation that rumors and misinformation are often more attractive than official information. [PERSON] et al. [14] considered CIM problem under a new diffusion-containment model and presented a \((1-1/e)\)-approximation algorithm. [PERSON] et al. [17] proposed distance based and wave propagation models in competitive influence process social networks. They showed that the objective function is submodular and devised a greedy algorithm with approximation ratio of \((1-1/e)\). Some other works propose an expanding LT model approach for CIM problem [12; 21; 22; 24]. For instance, [PERSON] et al. [24] proposed Competitive Linear Threshold models and provided some property results of these models. [PERSON] et al. [12] considered the problem of fair competitive viral marketing from the host's perspective. They proposed K-LT model and showed that the influence function is monotone and submodular. Generally, [PERSON] et al. [21] summarized two competitive influence models, which are extended from the IC model and the LT model, named Competitive Independent Cascade (CIC) and Competitive Linear Threshold (CLT) models. They also provided the properties of such models and categorized them by tie-breaking rules including fixed probability tie-breaking (TB-FP) rule and proportional probability tie-breaking (TB-PP) rule. TB-FP means that, when a node \(v\) is influenced by both competitors, it will be influenced by one of them with a fixed probability. TB-FP means that \(v\) becomes influenced by one competitor with a proportional probability. TB-FP reflects the dominance of a competitor and most purposed algorithms are based on this feature to give an approximation of \(1-1/e\). However, there is no approximation algorithm for TP-FP case.  
In other directions, [PERSON] et al. [15] proposed a community-based algorithm for CIM under DC model. Some variants of CIM have been studied. [PERSON] et al. [19] found the seed set with minimum cost set for threshold competitive influence problem. [PERSON] et al. [16], [PERSON] et al. [19] proposed competition and complementary approaches for CIM problem by extending IC model. The authors of [18] formulated Dominated Competitive Influence Maximization (DCIM) problem, which aims to maximize the difference in value between the influence of desired information and its competitors under a new competitive independent cascade model with meeting events.  
Different from most of the existing works, in this paper, we study a general problem of CIM, namely BCIM, which considers the CIM within budget and time constraints under condition of fair competition. We show that the objective function is not submodular and calculate that the objective function is #P-Hard. To overcome this challenge, we propose a randomized algorithm based on Sandwich approximation and polling-based method.