Optimization from Structured Samples for Coverage Functions
Authors: Wei Chen, Xiaoming Sun, Jialin Zhang, Zhijie Zhang
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that under three general assumptions on the sample distributions, we can design efficient OPSS algorithms that achieve a constant approximation for the maximum coverage problem. We further prove a constant lower bound under these assumptions, which is tight when not considering computational efficiency. Moreover, we also show that if we remove any one of the three assumptions, OPSS for the maximum coverage problem has no constant approximation. |
| Researcher Affiliation | Collaboration | 1Microsoft Research Asia, Beijing, China. 2CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China. 3School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing, China. |
| Pseudocode | Yes | Algorithm 1 OPSS algorithm for the general Assumption 1 |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | This is a theoretical paper and does not involve experiments with datasets. |
| Dataset Splits | No | This is a theoretical paper and does not involve experiments with datasets, thus no dataset splits are provided. |
| Hardware Specification | No | This is a theoretical paper and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper and does not list any software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper and does not describe any experimental setup or hyperparameters. |