Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm

Tasuku Soma, Naonori Kakimura, Kazuhiro Inaba, Ken-ichi Kawarabayashi
; Proceedings of the 31st International Conference on Machine Learning, PMLR 32(1):351-359, 2014.

Abstract

We consider the budget allocation problem over bipartite influence model proposed by Alon et al. This problem can be viewed as the well-known influence maximization 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 maximization over integer lattice subject to a knapsack 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 probabilities are nonincreasing, we obtain a faster (1-1/e)-approximation algorithm, which runs essentially in linear time in the number of nodes. This allows us to implement our algorithm up to almost 10M edges (indeed, our experiments tell us that we can implement our algorithm up to 1 billion edges. It would approximately take us only 500 seconds.).

Cite this Paper


BibTeX
@InProceedings{pmlr-v32-soma14, title = {Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm}, author = {Tasuku Soma and Naonori Kakimura and Kazuhiro Inaba and Ken-ichi Kawarabayashi}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {351--359}, year = {2014}, editor = {Eric P. Xing and Tony Jebara}, volume = {32}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/soma14.pdf}, url = {http://proceedings.mlr.press/v32/soma14.html}, abstract = {We consider the budget allocation problem over bipartite influence model proposed by Alon et al. This problem can be viewed as the well-known influence maximization 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 maximization over integer lattice subject to a knapsack 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 probabilities are nonincreasing, we obtain a faster (1-1/e)-approximation algorithm, which runs essentially in linear time in the number of nodes. This allows us to implement our algorithm up to almost 10M edges (indeed, our experiments tell us that we can implement our algorithm up to 1 billion edges. It would approximately take us only 500 seconds.).} }
Endnote
%0 Conference Paper %T Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm %A Tasuku Soma %A Naonori Kakimura %A Kazuhiro Inaba %A Ken-ichi Kawarabayashi %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-soma14 %I PMLR %J Proceedings of Machine Learning Research %P 351--359 %U http://proceedings.mlr.press %V 32 %N 1 %W PMLR %X We consider the budget allocation problem over bipartite influence model proposed by Alon et al. This problem can be viewed as the well-known influence maximization 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 maximization over integer lattice subject to a knapsack 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 probabilities are nonincreasing, we obtain a faster (1-1/e)-approximation algorithm, which runs essentially in linear time in the number of nodes. This allows us to implement our algorithm up to almost 10M edges (indeed, our experiments tell us that we can implement our algorithm up to 1 billion edges. It would approximately take us only 500 seconds.).
RIS
TY - CPAPER TI - Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm AU - Tasuku Soma AU - Naonori Kakimura AU - Kazuhiro Inaba AU - Ken-ichi Kawarabayashi BT - Proceedings of the 31st International Conference on Machine Learning PY - 2014/01/27 DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-soma14 PB - PMLR SP - 351 DP - PMLR EP - 359 L1 - http://proceedings.mlr.press/v32/soma14.pdf UR - http://proceedings.mlr.press/v32/soma14.html AB - We consider the budget allocation problem over bipartite influence model proposed by Alon et al. This problem can be viewed as the well-known influence maximization 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 maximization over integer lattice subject to a knapsack 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 probabilities are nonincreasing, we obtain a faster (1-1/e)-approximation algorithm, which runs essentially in linear time in the number of nodes. This allows us to implement our algorithm up to almost 10M edges (indeed, our experiments tell us that we can implement our algorithm up to 1 billion edges. It would approximately take us only 500 seconds.). ER -
APA
Soma, T., Kakimura, N., Inaba, K. & Kawarabayashi, K.. (2014). Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm. Proceedings of the 31st International Conference on Machine Learning, in PMLR 32(1):351-359

Related Material