Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm

We consider the budget allocation problem over bipartite influence model proposed by Alon et al. (Alon et al., 2012). This problem can be viewed as the well-known influence maximiza-tion problem with budget constraints. We first show that this problem and its much more general form fall into a general setting; namely the monotone submodular function max-imization over integer lattice subject to a knap-sack constraint. Our framework includes Alon et al.’s model, even with a competitor and with cost. We then give a (1 − 1/e)-approximation algorithm for this more general problem. Furthermore, when influence probabili