Fully Dynamic Online Selection through Online Contention Resolution Schemes
Authors: Vashist Avadhanula, Andrea Celli, Riccardo Colini-Baldeschi, Stefano Leonardi, Matteo Russo
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contribution is providing a general method for constructing an OCRS for fully dynamic online selection problems. Then, we show how to employ such OCRS to construct no-regret algorithms in a partial information model with semi-bandit feedback and adversarial inputs. and Theorem 1. Let F, Fd be the standard and temporal packing constraint families, respectively, and let their corresponding polytopes be PF and Pd F. Let x b PF and y b Pd F, and consider a (b, c)-selectable greedy OCRS π for Fπ,x. Then, Algorithm 1 equippend with π is a (b, c)-selectable greedy OCRS for Fd π,y. |
| Researcher Affiliation | Collaboration | Vashist Avadhanula1, Andrea Celli2, Riccardo Colini-Baldeschi1, Stefano Leonardi3, Matteo Russo3 1 Core Data Science, Meta, London, UK 2Department of Computing Sciences, Bocconi University, Milan, Italy 3Department of Computer, Control and Management Engineering Antonio Ruberti, Sapienza University, Rome, Italy |
| Pseudocode | Yes | Algorithm 1: Greedy OCRS Black-box Reduction, Algorithm 2: FULL-FEEDBACK ALGORITHM, Algorithm 3: SEMI-BANDIT-FEEDBACK ALGORITHM WITH ORACLE ACCESS TO OCRS |
| Open Source Code | No | The paper does not provide any statements about open-source code availability, nor does it include links to repositories or mention supplementary materials containing code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not conduct empirical studies; therefore, no dataset is used or referenced, nor is there any information about public availability of a dataset. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical studies; therefore, no dataset split information for training, validation, or testing is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies with version numbers, as it does not report on practical implementations or experiments. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and proofs rather than empirical evaluation. As such, it does not describe an experimental setup or provide hyperparameter details. |