Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm
Authors: Tasuku Soma, Naonori Kakimura, Kazuhiro Inaba, Ken-ichi Kawarabayashi
ICML 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We now verify our theoretical results by implementing Algorithm 2 for the budget allocation problem over bipartite influence model with nonincreasing influence probabilities. To demonstrate that the greedy choice indeed performs well, the expected number f(b) of activated nodes by the greedy choice is compared to that by other strategies. [...] Figures 1 and 2 are our simulation results on Yahoo! Search Marketing Advertiser Bidding Data (Yah!). [...] In order to implement our algorithms for larger scale graphs, we have also run our experiments on artificially generated graphs. Figures 3 and 4 are simulation results on synthesized graphs with |S| = 200, 000 and |T| = 2, 000, 000 nodes with around 8, 000, 000 edges between them. |
| Researcher Affiliation | Collaboration | Tasuku Soma TASUKU SOMA@MIST.I.U-TOKYO.AC.JP Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, 113-8656, and JST, ERATO, Kawarabayashi Large Graph Project, Tokyo, 101-8430 Naonori Kakimura KAKIMURA@GLOBAL.C.U-TOKYO.AC.JP College of Arts and Sciences, The University of Tokyo, Tokyo, 153-8902 Kazuhiro Inaba KINABA@GOOGLE.COM Google Inc. Ken-ichi Kawarabayashi K KENITI@NII.AC.JP National Institute of Informatics, JST, ERATO, Kawarabayashi Project, Tokyo, 101-8430 |
| Pseudocode | Yes | Algorithm 1 GREEDYPROCEDURE [...] Algorithm 2 SIMPLEGREEDYPROCEDURE |
| Open Source Code | No | The paper mentions the use of a dataset from Yahoo! ('Yahoo! webscope dataset: ydata-ysm-advertiser-bids-v1.0. http://research.yahoo.com/Academic_Relations.') but does not provide a link or statement about the availability of its own source code. |
| Open Datasets | Yes | Figures 1 and 2 are our simulation results on Yahoo! Search Marketing Advertiser Bidding Data (Yah!). [...] Yahoo! webscope dataset: ydata-ysm-advertiser-bids-v1.0. http://research.yahoo.com/Academic_Relations. |
| Dataset Splits | No | The paper describes using the Yahoo! Bidding Data and synthesized graphs for experiments but does not provide specific details on how these datasets were split into training, validation, or test sets. |
| Hardware Specification | Yes | Allocation of 1, 000 budgets in the greedy algorithm took 3.36 seconds (including the graph generation time) in average on a machine with Xeon E5-2690 2.9GHz CPU and 64GB memory. |
| Software Dependencies | No | The paper does not provide specific software dependencies, such as programming languages, libraries, or solvers, along with their version numbers, that would be needed to replicate the experiments. |
| Experiment Setup | Yes | For each s, we have set p(1) s a random value between 0 and P. Then, p(i+1) s is set to p(i) s X, where X is a random value between 0 and 1, generated for each i and s. Figures 1 and 2 show the results on P = 1 and P = 0.1 cases. |