Pandora's problem with nonobligatory inspection: optimal structure and a PTAS

DOI10.1145/3564246.3585217MaRDI QIDQ6499268zbMATH OpenFDO

Authors Hedyeh Beyhaghi, Linda Cai

Publication date 8 May 2024

Full work available at URL https://doi.org/10.1145/3564246.3585217

zbMATH Keywords

optimal searchPandora's boxpolynomial-time approximation scheme

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A PTAS for a class of stochastic dynamic programs
• Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items
• Optimal Search for the Best Alternative
• The price of information in combinatorial optimization
• Whether or not to open Pandora's box

Cited in

(5)

• Pandora's box problem with time constraints
• Matching with nested and bundled Pandora boxes
• Pandora's box problem over time
• Designing exploration contracts
• Non-adaptive evaluation of k-of-n functions: tight gap and a unit-cost PTAS

This page was built for publication: Pandora's problem with nonobligatory inspection: optimal structure and a PTAS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499268)