Personalized Lattice Influence Maximization: Approximation Guarantees and Robustness

Recently, personalized influence maximization, which generalizes classic influence maximization by wisely allocating personalized discounts to users, showed its superiority in achieving cost-effective marketing plans over traditional influence maximization techniques. However, under continuous cost reaction scenarios, it is hard to obtain the approximation guarantee. To this end, we first propose a personalized lattice influence maximization (PLIM) problem, which can be approximately guaranteed through a greedy algorithm from an innovative perspective, i.e., match item selection with a knapsack constraint (MIS-K). Furthermore, to address the practical challenges associated with accurately learning user purchase probabilities, we extend the proposed PLIM framework in the form of robust optimization. We develop a robust algorithm that achieves a solution-dependent approximation guarantee and analyze the computational hardness of approximating RPLIM. By introducing an innovative Re-arrangement Sampling technique, we demonstrate that sampling can effectively mitigate uncertainty in purchase probabilities, enabling a strong robust ratio of (1 −ε)(1 − 1/e) with high probability. Experimental results on multiple benchmark datasets confirm the effectiveness and efficiency of our proposed methods. © 2013 IEEE.