Weitzman's Rule for Pandora's Box with Correlations
Authors: Evangelia Gergatsouli, Christos Tzamos
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work we revisit PANDORA S BOX when the value distributions are correlated, first studied in Chawla et al. [2020]. We show that the optimal algorithm for the independent case, given by Weitzman s rule, directly works for the correlated case. In fact, our algorithm results in significantly improved approximation guarantees compared to the previous work, while also being substantially simpler. We also show how to implement the rule given only sample access to the correlated distribution of values. |
| Researcher Affiliation | Academia | Evangelia Gergatsouli University of Wisconsin-Madison evagerg@cs.wisc.edu Christos Tzamos University of Wisconsin-Madison & University of Athens tzamos@wisc.edu |
| Pseudocode | Yes | Algorithm 1: Weitzman s algorithm, for correlated D. Algorithm 2: Weitzman s rule for Partial Updates Algorithm 3: Weitzman s rule for Full Updates Algorithm 4: General format of PANDORA S BOX algorithm. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository. |
| Open Datasets | No | The paper is theoretical and discusses properties of distributions and sampling for analytical purposes (e.g., learnability), but does not use or provide access information for a publicly available dataset for empirical training. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup or specific hardware used. |
| Software Dependencies | No | The paper is theoretical and does not describe any software dependencies with specific version numbers. |
| Experiment Setup | No | The paper is theoretical and does not provide details on experimental setup, hyperparameters, or training configurations. |