Single-Sample Prophet Inequalities: A Combinatorial to Single-Item Reduction

Shuchi Chawla, Trung Dang

We study single-sample prophet inequalities for online combinatorial allocation. Our main contribution is a general reduction from combinatorial to single-item prophet inequalities…