Submodular Maximization in Clean Linear Time
Authors: Wenxin Li, Moran Feldman, Ehsan Kazemi, Amin Karbasi
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 6 Experimental Results We have studied the submodular maximization problem subject to different constraints. In this section, we compare our proposed algorithms with the state-of-the-art algorithms under the following constraints: (i) a carnality constraint (Section 6.1), (ii) a single knapsack constraint (Section 6.2), and (iii) combination of a p-system and d knapsack constraints (Appendix J.4). ... In our first experiment, we implement a movie recommender system by finding a diverse set of movies for a user. We adopt the approach of Lindgren et al. [54] to extract features for each movie by using ratings from the Movie Lens dataset [31]. ... From Figures 1c and 1d, we observe that Algorithm 2 significantly outperforms the other two algorithms with respect to both the utility and number of oracle calls metrics. |
| Researcher Affiliation | Collaboration | Wenxin Li The Ohio State University li.7328@osu.edu Moran Feldman University of Haifa moranfe@cs.haifa.ac.il Ehsan Kazemi Google ehsankazemi@google.com Amin Karbasi Yale University, Google Research amin.karbasi@yale.edu. |
| Pseudocode | Yes | Algorithm 1: FAST THRESHOLD GREEDY(ε, α)... Algorithm 2: FAST THRESHOLD GREEDY + POST-PROCESSING(ε)... Algorithm 3: Basic Algorithm(λ, ρ) |
| Open Source Code | No | The paper states "Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes]", but it does not provide a direct link to a code repository or an unambiguous statement about releasing the source code for the described methodology. |
| Open Datasets | Yes | In our first experiment, we implement a movie recommender system by finding a diverse set of movies for a user. We adopt the approach of Lindgren et al. [54] to extract features for each movie by using ratings from the Movie Lens dataset [31]. |
| Dataset Splits | No | The paper mentions using datasets for experiments (e.g., Movie Lens dataset) but does not provide specific details on how the data was split into training, validation, or test sets. |
| Hardware Specification | No | The paper does not provide specific hardware details such as exact GPU/CPU models, processor types, or memory amounts used for running its experiments. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers (e.g., library or solver names with version numbers) needed to replicate the experiment. |
| Experiment Setup | Yes | FASTTHRESHOLDGREEDY with ε {0.1, 0.2} performs as good as LAZYGREEDY... Execute Algorithm 1 with α = ε 1. |