2 papers
cs.DS2025
Optimal 4-Approximation for the Correlated Pandora's Problem
Nikhil Bansal, Zhiyi Huang, Zixuan Zhu
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 a…
cs.DS2025
Edge-weighted Matching in the Dark
Zhiyi Huang, Enze Sun, Xiaowei Wu +1
We present a -competitive Quadratic Ranking algorithm for the Oblivious Bipartite Matching problem, a distribution-free version of Query-Commit Matching. This result breaks…