Profit Maximization problem with Coupons in social networks

Viral marketing has become one of the most effective marketing strategies. In the process of real commercialization, in order to let some seed individuals know the products, companies can provide free samples to them. However, for some companies, especially famous ones, they are more willing to offer coupons than give samples. In this paper, we consider the Profit Maximization problem with Coupons (PM-C) in our new diffusion model named the Independent Cascade Model with Coupons and Valuations (IC-CV). To solve this problem, we propose the PMCA algorithm which can return a (1/3-epsilon)-approximate solution with at least 1 - 2n(-l) probability, and runs in O(log(np) . mn(3) logn(l logn n log2)/epsilon(3)) expected time. Furthermore, during the analysis we provide a method to estimate the non-monotone submodular function. (C) 2019 Elsevier B.V. All rights reserved.