Efficient Approximation Algorithms for Adaptive Target Profit Maximization

摘要: Given a social network $G$, the profit maximization (PM) problem asks for set of seed nodes to maximize profit, i.e., revenue influence spread less cost selection. The target (TPM) problem, which generalizes PM aims select subset from user $T$ profit. Existing algorithms mostly consider nonadaptive setting, where all are selected in one batch without any knowledge on how they may other users. In this paper, we study TPM adaptive users through multiple batches, such that selection exploits actual previous batches. To acquire an overall understanding, under both oracle model and noise model, propose ADG AddATP address them with strong theoretical guarantees, respectively. addition, better handle sampling errors idea hybrid error based design novel algorithm HATP boosts efficiency significantly. We conduct extensive experiments real networks evaluate performance, experimental results strongly confirm superiorities effectiveness our solutions.