Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Recurrent Submodular Welfare and Matroid Blocking Semi-Bandits
Authors: Orestis Papadigenopoulos, Constantine Caramanis
NeurIPS 2021 | Venue PDF | 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 EMAIL Constantine Caramanis Electrical and Computer Engineering The University of Texas at Austin EMAIL |
| 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. |