A Near Linear Query Lower Bound for Submodular Maximization
Authors: Binghui Peng, Aviad Rubinstein
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We strengthen their lower bound to a nearly tight eΩ(n). This lower bound holds even for estimating the value of the optimal subset. When the objective function is additive, we prove that finding an approximately optimal subset still requires near-linear query complexity, but we can estimate the value of the optimal subset in e O(n/k) queries, and that this is tight up to polylog factors. |
| Researcher Affiliation | Academia | 1Department of Computer Science, Stanford University, United States 2Department of Computer Science, Stanford University, United States. Correspondence to: Binghui Peng <EMAIL>, Aviad Rubinstein <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 Reduction: From submodular maximization to distributed set detection Algorithm 2 LINEARSUM(f, k) Algorithm 3 ESTIMATEQUANTILE(g, t) |
| Open Source Code | No | The paper is theoretical, focusing on lower bounds and algorithm design and analysis. There is no mention of releasing code, links to repositories, or supplementary materials containing implementation code for the described methodologies. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical proofs and algorithm design. It does not utilize any specific datasets for experimental evaluation, thus no information about public availability of datasets is provided. |
| Dataset Splits | No | The paper does not conduct experiments on datasets; therefore, there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and presents mathematical proofs and algorithm designs. It does not describe any experimental setup that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and lower bounds. It does not describe any empirical evaluations that would necessitate listing specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and primarily presents mathematical proofs and algorithm analysis. It does not include any experimental setup details such as hyperparameters or specific training configurations. |