讲座名称：Optimal 4-Approximation for the Correlated Pandora’s Problem
讲座时间：2025-06-13 09:30
讲座地点：清水河校区4号科研楼A区518
特邀专家：黄志毅，香港大学教授。研究成果主要在于探索不确定性下的序列决策算法（在线算法）、基于不同信息形式的学习理论（学习理论）、激励自利主体共享私有信息的机制设计（机制设计），以及在保密某些信息的同时披露另类信息的技术（差分隐私）。
讲座内容：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.
