Maximization of Approximately Submodular Functions
Authors: Thibaut Horel, Yaron Singer
NeurIPS 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide both lower and upper bounds: for ε > n 1/2 we show an exponential query-complexity lower bound. In contrast, when ε < 1/k or under a stronger bounded curvature assumption, we give constant approximation algorithms. |
| Researcher Affiliation | Academia | Thibaut Horel Harvard University thorel@seas.harvard.edu Yaron Singer Harvard University yaron@seas.harvard.edu |
| Pseudocode | No | The paper describes the 'greedy algorithm' and refers to its 'detailed description... in the appendix', but no explicit pseudocode or algorithm block is present in the provided text. |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not describe experiments using datasets, thus no information on dataset availability or access is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments with data, so no information about training, validation, or test splits is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe running experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe implementations or require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific hyperparameters or training configurations. |