Journal
THEORETICAL COMPUTER SCIENCE
Volume 803, Issue -, Pages 22-35Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2019.03.007
Keywords
Profit Maximization; Social network; Approximation algorithm
Categories
Funding
- National Natural Science Foundation of China [11871442]
- China Postdoctoral Science Foundation [2016M600556]
- Qingdao Postdoctoral Application Research Project [2016156]
- Natural Science Foundation of Shandong Province of China [ZR2017QA010]
- Fundamental Research Funds for the Central Universities
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available