您所在的位置: 首页- 新闻公告- 学术讲座-

学术讲座

学术前沿讲座第25期:Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme
日期:2022-11-28访问量:

学术前沿25.png

报告题目: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.

主讲嘉宾

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

检测到您当前使用浏览器版本过于老旧,会导致无法正常浏览网站;请您使用电脑里的其他浏览器如:360、QQ、搜狗浏览器的速模式浏览,或者使用谷歌、火狐等浏览器。

下载Firefox