Submodular Maximization beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
Authors: Chris Harshaw, Moran Feldman, Justin Ward, Amin Karbasi
ICML 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We empirically demonstrate the success of our algorithms by applying them to experimental design on the Boston Housing dataset and directed vertex cover on the Email EU dataset. |
| Researcher Affiliation | Academia | 1Department of Computer Science, Yale University, New Haven, USA 2Department of Mathematics and Computer Science, Open University of Israel, Raanana, Israel 3School of Mathematical Sciences, Queen Mary University of London, London, UK 4Department of Electrical Engineering, Yale University, New Haven, USA. |
| Pseudocode | Yes | Algorithm 1 DISTORTED GREEDY; Algorithm 2 STOCHASTIC DISTORTED GREEDY; Algorithm 3 UNCONSTRAINED DISTORTED GREEDY; Algorithm 4 γ-SWEEP |
| Open Source Code | Yes | Source code available at https://github.com/ crharshaw/submodular-minus-linear |
| Open Datasets | Yes | For this experiment, we used the Boston Housing dataset (Jr. & Rubenfield, 1978), a standard benchmark dataset containing d = 14 attributes of n = 506 Boston homes... For our experiments, we use the EU Email Core network, a directed graph generated using email data from a large European research institution (Yin et al., 2017; Leskovec et al., 2007). |
| Dataset Splits | No | The paper mentions using established datasets like Boston Housing and EU Email Core, but it does not specify explicit training, validation, and test splits (e.g., percentages or counts) within the text for reproducibility. It discusses varying cardinality constraints and cost penalties in experiments. |
| Hardware Specification | Yes | Experiments were run on a 2015 Mac Book Pro with 3.1 GHz Intel Core i7 and 8 GB DDR3 SDRAM |
| Software Dependencies | No | The paper mentions 'The code was written using the Julia programming language, version 1.0.2'. While a specific version of Julia is given, no other software libraries or dependencies with their versions are listed, which is required for reproducibility. |
| Experiment Setup | Yes | As there is no specified cost per measurement, we assigned costs proportionally to initial marginal gains in utility; that is, ce = αg(e) for some α [0, 1]. We set σ = 1/d, and randomly generated a normal prior with covariance Σ = ADAT , where A is randomly chosen as Ai,j N(0, 1) and D is diagonal with Di,i = (i/d)2. |