Simple and Optimal Greedy Online Contention Resolution Schemes
Authors: Vasilis Livanos
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 6 Experimental Results In this section, we present our experimental results which give a quantitative view into how our greedy OCRSs outperform the former state-of-the-art greedy OCRSs by [FSZ16]. For the constraint system, we consider both the single-item setting as well as randomly-generated transversal matroid constraints. The code used to run these experiments can be found in the supplementary material. |
| Researcher Affiliation | Academia | Vasilis Livanos Department of Computer Science University of Illinois Urbana-Champaign Urbana, IL 61801 livanos3@illinois.edu |
| Pseudocode | No | The paper describes algorithms in prose within the text (e.g., 'π will draw a random set R(q)...') but does not present them in structured pseudocode or algorithm blocks. |
| Open Source Code | Yes | The code used to run these experiments can be found in the supplementary material. |
| Open Datasets | No | The paper generates its own instances for experiments (e.g., 'randomly-generated transversal matroid constraints') and does not use or provide access information for a publicly available dataset. |
| Dataset Splits | No | The paper conducts simulations rather than using traditional datasets with training, validation, and testing splits. |
| Hardware Specification | No | The paper does not provide any specific hardware details (e.g., GPU/CPU models, memory specifications) used for running the experiments. |
| Software Dependencies | No | The paper mentions that code is available in supplementary material but does not list any specific software dependencies with version numbers. |
| Experiment Setup | Yes | For our experiments, we have the following parameters: N: The number of elements. For the single item setting, this varies from 10 to 100. For the transversal matroid constraint, this is set to 50. ITERATIONS: For a fixed x, the number of times we simulate the realization of the elements. This is used to approximate the selectability of each element within a reasonable estimate and is set to 200, 000. REPETITIONS: The number of times we run the entire experiment from scratch. This has no effect on the uniform instance of the single-item setting or the transversal matroid constraint, but affects the random vector x in the randomly-generated instance of the single-item setting, and is set to 10. |