Optimal 4-Approximation for the Correlated Pandora's Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912640138215424 |
|---|---|
| author | Bansal, Nikhil Huang, Zhiyi Zhu, Zixuan |
| author_facet | Bansal, Nikhil Huang, Zhiyi Zhu, Zixuan |
| contents | The Correlated Pandora's Problem posed by Chawla et al. (2020) generalizes the classical Pandora's Problem by allowing the numbers inside the Pandora's boxes to be correlated. It also generalizes the Min Sum Set Cover problem, and is related to the Uniform Decision Tree problem. This paper gives an optimal 4-approximation for the Correlated Pandora's Problem, matching the lower bound of 4 from Min Sum Set Cover. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_17029 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal 4-Approximation for the Correlated Pandora's Problem Bansal, Nikhil Huang, Zhiyi Zhu, Zixuan Data Structures and Algorithms The Correlated Pandora's Problem posed by Chawla et al. (2020) generalizes the classical Pandora's Problem by allowing the numbers inside the Pandora's boxes to be correlated. It also generalizes the Min Sum Set Cover problem, and is related to the Uniform Decision Tree problem. This paper gives an optimal 4-approximation for the Correlated Pandora's Problem, matching the lower bound of 4 from Min Sum Set Cover. |
| title | Optimal 4-Approximation for the Correlated Pandora's Problem |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.17029 |