Pandora's Box Problem with Order Constraints

• 成果类型: Article
• 署名作者: Boodaghians, Shant; Fusco, Federico; Lazos, Philip; Leonardi, Stefano
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; Sapienza University Rome
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1271
• 发表日期: 2023
• 页码: 498-519
• 关键词: Approximation; optimization; search

摘要

The Pandora's Box problem, originally posed by Weitzman in 1979, models selection from a set of random-valued alternatives-the boxes-when evaluation is costly. Weitzman showed that the Pandora's Box problem admits a simple threshold-based solution that considers the options in decreasing order of reservation value, a proxy for the actual value of the boxes in the exploration process. We study for the first time this problem when the order in which the boxes are opened is constrained, forcing the solution to account for both the depth of search, as opening a box gives access to more boxes, and the breadth, as there are many directions to explore. Despite these difficulties, we show that greedy optimal strategies exist and can be efficiently computed for tree-like order constraints. We also prove that finding optimal adaptive search strategies is NP-hard to approximate (up to a certain constant) when certain matroid constraints are applied to further restrict the set of boxes that may be opened or when the order constraints are given as reachability constraints on a directed acyclic graph. We complement this hardness result by giving efficient approximation algorithms, exploiting a low adaptivity gap for a carefully relaxed version of the problem.