A Dynamic Algorithm for Weighted Submodular Cover Problem
Authors: Kiarash Banihashem, Samira Goudarzi, Mohammadtaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We initiate the study of the submodular cover problem in dynamic setting where the elements of the ground set are inserted and deleted. ... For this problem, we propose a randomized algorithm that, in expectation, obtains a (1 O(ϵ), O(ϵ 1))-bicriteria approximation using polylogarithmic query complexity per update. |
| Researcher Affiliation | Academia | 1Department of Computer Science, University of Maryland, MD, USA 2Department of Mathematics and Computer Science, TU Eindhoven, the Netherlands. Correspondence to: Samira Goudarzi <samirag@umd.edu>, Kiarash Banihashem <kiarash@umd.edu>. |
| Pseudocode | Yes | Algorithm 1 Parallel Runs ... Algorithm 2 Data Structure Construction ... Algorithm 3 Insertion ... Algorithm 4 Deletion ... Algorithm 5 CALCSAMPLESIZE |
| Open Source Code | No | The paper does not provide any explicit statement or link indicating the release of open-source code for the described methodology. |
| Open Datasets | No | This paper is theoretical and does not involve empirical experiments with datasets for training, validation, or testing. |
| Dataset Splits | No | This paper is theoretical and does not involve empirical experiments with datasets for training, validation, or testing. |
| Hardware Specification | No | This paper is theoretical and does not involve empirical experiments, so no hardware specifications are mentioned. |
| Software Dependencies | No | This paper is theoretical and does not involve empirical experiments, so no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | This paper is theoretical and does not involve empirical experiments, so no experimental setup details like hyperparameters or training settings are provided. |