Recurrent Submodular Welfare and Matroid Blocking Semi-Bandits
Authors: Orestis Papadigenopoulos, Constantine Caramanis
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we develop the novel technique of correlated (interleaved) scheduling, which allows us to obtain a polynomial-time (1 - 1/e)-approximation algorithm (asymptotically and in expectation) for any matroid. Along the way, we discover an interesting connection to a variant of Submodular Welfare Maximization, for which we provide (asymptotically) matching upper and lower approximability bounds. |
| Researcher Affiliation | Academia | Orestis Papadigenopoulos Department of Computer Science The University of Texas at Austin papadig@cs.utexas.edu Constantine Caramanis Electrical and Computer Engineering The University of Texas at Austin constantine@utexas.edu |
| Pseudocode | Yes | Algorithm 3.1 (INTERLEAVED-SUBMODULAR (IS)). For each element i ∈ A, let ri ∼ U[0, 1] be a random offset drawn uniformly from [0, 1]. At every round t = 1, 2, . . . , let At ⊆ A be the subset of elements such that for any i ∈ At, the interval Li,t = [t − 1/di + ri, (t + 1) − 1/di + ri) contains an integer. Choose the elements At and collect the reward f(At). |
| 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 paper is theoretical and focuses on algorithm design and analysis. It does not describe experiments involving dataset training or specify publicly available datasets for such purposes. |
| Dataset Splits | No | This paper is theoretical and focuses on algorithm design and analysis. It does not describe experiments involving dataset validation or specific dataset split information for validation. |
| Hardware Specification | No | This is a theoretical paper and does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | This is a theoretical paper and does not list any specific software dependencies with version numbers required to replicate experimental setups or results. |
| Experiment Setup | No | This paper is theoretical and does not describe an empirical experimental setup with specific hyperparameters, training configurations, or system-level settings. |