Robust Sequence Submodular Maximization
Authors: Gamal Sallam, Zizhan Zheng, Jie Wu, Bo Ji
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | To address these unique challenges, we design two robust greedy algorithms: while one algorithm achieves a constant approximation ratio but is robust only against the removal of a subset of contiguous elements, the other is robust against the removal of an arbitrary subset of the selected elements but requires a stronger assumption and achieves an approximation ratio that depends on the number of the removed elements. Finally, we generalize the analyses to considering sequence functions under weaker assumptions based on approximate versions of sequence submodularity and backward monotonicity. |
| Researcher Affiliation | Academia | Gamal Sallam1, Zizhan Zheng2, Jie Wu1, and Bo Ji 1, 3 1Department of Computer and Information Sciences, Temple University 2Department of Computer Science, Tulane University 3Department of Computer Science, Virginia Tech |
| Pseudocode | Yes | Algorithm 1 Robust greedy algorithm against the removal of contiguous elements; Algorithm 2 Robust greedy algorithm against the removal of arbitrary elements |
| Open Source Code | No | The paper does not provide any concrete access information (e.g., repository links, explicit statements of code release) for open-source code related to the described methodology. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and approximation guarantees. It does not conduct empirical studies with datasets, thus no information about public datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits. Therefore, it does not specify training/test/validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and analysis. It does not describe any empirical experiments, and therefore no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and analysis. It does not describe any empirical experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and describes algorithms and their theoretical guarantees, not an experimental setup. Therefore, it does not contain specific experimental setup details like hyperparameters or training configurations. |