Optimization for Approximate Submodularity
Authors: Yaron Singer, Avinatan Hassidim
NeurIPS 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we describe a technique that yields strong guarantees for maximization of monotone submodular functions from approximate surrogates under cardinality and intersection of matroid constraints. In particular, we show tight guarantees for maximization under a cardinality constraint and 1/(1 + P) approximation under intersection of P matroids. |
| Researcher Affiliation | Collaboration | Avinatan Hassidim Bar Ilan University and Google avinatan@cs.biu.ac.il Yaron Singer Harvard University yaron@seas.harvard.edu |
| Pseudocode | Yes | Algorithm 1 SM-GREEDY; Algorithm 2 SM-MATROID-GREEDY |
| Open Source Code | No | The paper does not provide concrete access to source code. |
| Open Datasets | No | This is a theoretical paper that does not use or reference any datasets for training. |
| Dataset Splits | No | This is a theoretical paper and does not describe data splitting for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper and does not specify any software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper and does not describe an experimental setup with hyperparameters or training configurations. |