期刊
THEORETICAL COMPUTER SCIENCE
卷 803, 期 -, 页码 22-35出版社
ELSEVIER
DOI: 10.1016/j.tcs.2019.03.007
关键词
Profit Maximization; Social network; Approximation algorithm
资金
- 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
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据