Monotone k-Submodular Function Maximization with Size Constraints
Authors: Naoto Ohsaka, Yuichi Yoshida
NeurIPS 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | To show the practicality of our algorithms, we apply them to the influence maximization problem and the sensor placement problem, and we demonstrate that they outperform previous methods based on submodular function maximization and several baseline methods in terms of the solution quality. |
| Researcher Affiliation | Collaboration | Naoto Ohsaka The University of Tokyo ohsaka@is.s.u-tokyo.ac.jp Yuichi Yoshida National Institute of Informatics, and Preferred Infrastructure, Inc. yyoshida@nii.ac.jp |
| Pseudocode | Yes | Algorithm 1 k-Greedy-TS; Algorithm 2 k-Stochastic-Greedy-TS; Algorithm 3 k-Greedy-IS; Algorithm 4 k-Stochastic-Greedy-IS |
| Open Source Code | No | The paper does not provide any specific links or explicit statements about the availability of its source code. |
| Open Datasets | Yes | We use a publicly available real-world dataset of a social news website Digg.1 This dataset consists of a directed graph where each vertex represents a user and each edge represents the friendship between a pair of users, and a log of user votes for stories. (Footnote: 1http://www.isi.edu/ lerman/downloads/digg2009.html); We use the publicly available Intel Lab dataset.2 This dataset contains a log of approximately 2.3 million readings collected from 54 sensors deployed in the Intel Berkeley research lab between February 28th and April 5th, 2004. (Footnote: 2http://db.csail.mit.edu/labdata/labdata.html) |
| Dataset Splits | No | The paper does not specify distinct training, validation, and test dataset splits in the context of model learning. It describes simulations and evaluations on datasets. |
| Hardware Specification | Yes | We conducted experiments on a Linux server with Intel Xeon E5-2690 (2.90 GHz) and 264GB of main memory. |
| Software Dependencies | No | The paper states 'We implemented all algorithms in C++' but does not provide specific version numbers for C++ or any other software libraries or dependencies used. |
| Experiment Setup | Yes | We set the number of topics k to be 10, and estimated edge probabilities on each topic from the log using the method of [1]. We set the value of B to 5, 10, . . . , 100... We chose δ = 0.1... the influence spread was approximated by simulating the diffusion process 100 times. When the algorithms terminate, we simulated the diffusion process 10,000 times to obtain sufficiently accurate estimates of the influence spread... We set B1 = B2 = B3 = b, where b is a parameter varying from 1 to 18. |