Research map / Learning theory and algorithms / Submodular and game algorithms
Weitzman's Rule for Pandora's Box with Correlations
Evangelia Gergatsouli, Christos Tzamos
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Generalize Weitzman's reservation values to correlated distributions and use partial updates | Weitzman's rule for Pandora's Box · Pandora's Box with correlated distributions | approximation ratio: 9.22 -> 4.428 | Improved |
| Use full updates conditioned on the exact value revealed instead of partial updates | Weitzman's rule for Pandora's Box · Pandora's Box with correlated distributions | approximation ratio: 9.22 -> 5.828 | Improved |
| Use partial updates rather than full updates (ablation) | Weitzman's rule for Pandora's Box · Pandora's Box with correlated distributions | approximation ratio: 5.828 -> 4.428 | Improved |
| Learn the partial-update policy from polynomially many samples | Weitzman's rule, partial updates · Pandora's Box with correlated distributions, sample access | approximation ratio: 4.428 -> 4.428 + ε | Improved |
| Use full Bayesian updates with sample access rather than full distribution knowledge | Weitzman's rule, full updates · Pandora's Box with correlated distributions, sample access | learnability | Hurt |
Closest papers by meaning
- Contextual Pandora’s Box (AAAI 2024 · similarity 0.86)
- Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index (NeurIPS 2024 · similarity 0.86)
- Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · similarity 0.84)
- Pandora’s Problem with Deadlines (AAAI 2024 · similarity 0.83)
- Resolution of Simpson's paradox via the common cause principle (NeurIPS 2025 · similarity 0.81)
- Forecasting Competitions with Correlated Events (AAAI 2025 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
