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 = {Soma, Tasuku and Kakimura, Naonori and Inaba, Kazuhiro and Kawarabayashi, Ken-ichi}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {351--359}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, 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 = {https://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 %P 351--359 %U https://proceedings.mlr.press/v32/soma14.html %V 32 %N 1 %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 DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-soma14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 1 SP - 351 EP - 359 L1 - http://proceedings.mlr.press/v32/soma14.pdf UR - https://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 Proceedings of Machine Learning Research 32(1):351-359 Available from https://proceedings.mlr.press/v32/soma14.html.

Related Material