Accelerated Best-First Search With Upper-Bound Computation for Submodular Function Maximization
Authors: Shinsaku Sakaue, Masakazu Ishihata
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments show that our accelerated BFS is far more efficient in terms of both time and space complexities than existing methods. |
| Researcher Affiliation | Collaboration | Shinsaku Sakaue NTT Communication Science Laboratories sakaue.shinsaku@lab.ntt.co.jp Masakazu Ishihata Hokkaido University ishihata.masakazu@ist.hokudai.ac.jp |
| Pseudocode | Yes | Algorithm 1 BFSTC(U, g( ), c U, B, α); Algorithm 2 Greedy SK(V, g S( ), c V , BS); Algorithm 3 Greedy Add(V, g S( ), c V , BS) |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code for the described methodology, nor does it include links to a code repository. |
| Open Datasets | Yes | COV: The COV instance uses a dataset on messages exchanged by 899 users on 522 topics (Opsahl 2013). https://toreopsahl.com/datasets/#online forum network. LOC: The LOC instance uses a dataset on 473 subway stations in New York City (NYC) (Roest and Mashariki 2015). https://data.cityofnewyork.us/Transportation/Subway-Stations/arq3-7z49/data. INF: The INF instance uses the Movie Lens 100K dataset (Harper and Konstan 2015). https://grouplens.org/datasets/movielens/. |
| Dataset Splits | No | The paper describes the datasets used for experiments but does not provide specific details on train/validation/test splits (e.g., percentages or sample counts) for reproducibility. |
| Hardware Specification | Yes | All experiments were conducted on a 64-bit Cent7.3.1611 machine with Xeon 5E-2697 v3 2.6 GHz CPUs and 256 GB of RAM. |
| Software Dependencies | No | The paper mentions the operating system '64-bit Cent7.3.1611' but does not specify any programming languages, libraries, or other software dependencies with version numbers used for the experiments. |
| Experiment Setup | Yes | In all instances, we set |U| = 100 and B = 1. The costs cv (v U) are drawn randomly from a uniform distribution on [0, 1]... In COV instances, wi are drawn from u[0,1], and each v U randomly covers each w W with probability 0.3. |