Dynamic Constrained Submodular Optimization with Polylogarithmic Update Time
Authors: Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, Mohammadtaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we develop a simpler algorithm for the problem that maintains a ( 1/2 ϵ)-approximate solution for submodular maximization under cardinality constraint k using a polylogarithmic amortized update time. ... In this paper, we answer the polylogarithmic question affirmatively; we develop a new simpler algorithm which maintains a ( 1/2 ϵ)-approximate solution for submodular maximization problem under cardinality constraint k with a poly-logarithmic amortized query complexity. ... In this section, we analyze the query complexity of our algorithm. ... To prove this result, we establish two theorems that consider the approximation factor and query complexity of our algorithm, respectively. |
| Researcher Affiliation | Academia | 1Department of Computer Science, University of Maryland, MD, USA 2Department of Mathematics and Computer Science, TU Eindhoven, the Netherlands. |
| Pseudocode | Yes | Algorithm 1 Offline algorithm; Algorithm 2 Insert; Algorithm 3 Delete; Algorithm 4 CALCSAMPLECOUNT |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code or provide links to a code repository for the described methodology. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and analysis. It does not describe experiments using datasets, thus no information on training datasets or their availability is present. |
| Dataset Splits | No | The paper is theoretical and focuses on algorithm design and analysis. It does not describe empirical experiments with data, so no training, validation, or test split information is provided. |
| Hardware Specification | No | The paper describes a theoretical algorithm and its analysis, not empirical experiments. Therefore, no hardware specifications for running experiments are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and analysis. It does not describe empirical experiments or specific software dependencies with version numbers needed for replication. |
| Experiment Setup | No | The paper describes a theoretical algorithm and its analysis, not empirical experiments. Therefore, no details about an experimental setup, such as hyperparameters or training settings, are provided. |