Profit maximization for competitive social advertising
| Autor: | Jiawei Chen, Chun Chen, Yan Feng, Sheng Zhou, Yanhao Huang, Can Wang, Deshi Ye, Qihao Shi |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
General Computer Science
Computer science Profit maximization Social platform Advertising 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Effective algorithm Set (abstract data type) 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Host (network) |
| Zdroj: | Theoretical Computer Science. 868:12-29 |
| ISSN: | 0304-3975 |
| Popis: | In social advertising, the social platform host may run marketing campaigns for multiple competing clients simultaneously. In this case, each client comes up with a budget and an influence spread requirement. The host runs campaigns by allocating a set of seed nodes for each client. If the influence spread triggered by a seed set meets the requirement, the host can earn the budget from the corresponding client. In this paper, we study the problem of Profit Maximization, considering that different seeds incur different costs. Given all the clients' requirements met, we aim to find the optimal seed allocation with minimum cost. Under the competitive K-LT propagation model, we show the Profit Maximization problem is NP-hard and NP-hard to approximate with any factor. To find a feasible solution, we propose an effective algorithm that iteratively selects a candidate set and obtains an approximate allocation. The experimental results over a real-world dataset validate the effectiveness of the proposed methods. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect