学术讲座

报告题目：Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme

讲座时间：2022年11月28日（周一）10:00-11:30

腾讯会议：543-155-411

报告摘要：Weitzman (1979) introduced the Pandora Box problem as a model for sequential search with inspection costs, and gave an elegant index-based policy that attains provably optimal expected payoff.  In various scenarios, the searching agent may select an option without making a costly inspection.  The variant of the Pandora box problem with non-obligatory inspection has attracted interest from both economics and algorithms researchers.  Various simple algorithms have proved suboptimal, with the best known 0.8-approximation algorithm due to Guha et al. (2008).  No hardness result for the problem was known.  In this work, we show that it is NP-hard to compute an optimal policy for Pandora's problem with nonobligatory inspection.  We also give a polynomial-time approximation scheme (PTAS) that computes policies with expected payoff arbitrarily close to the optimal.  On the side, we show the decision version of the problem to be in NP.

主讲嘉宾

伏虎是上海财经大学理论计算机中心副教授，研究兴趣主要为计算经济学和在线算法。他从康奈尔大学获博士学位，曾在微软研究院新英格兰实验室、加州理工做博后工作，归国前在加拿大英属哥伦比亚大学计算机系任助理教授。