Abstract

We study matroid prophet inequalities when distributions are unknown and accessible only through samples. While single-sample prophet inequalities for special matroids are known, no constant-factor competitive algorithm with even a sublinear number of samples was known for general matroids. Adding more to the stake, the single-sample version of the question for general matroids has close (two-way) connections with the long-standing matroid secretary conjecture.

In this work, we give a $(1/4-\epsilon)$-competitive matroid prophet inequality with only $O_\epsilon(\poly \log n)$ samples. Our algorithm consists of two parts: (i) a novel quantile-based reduction from matroid prophet inequalities to online contention resolution schemes (OCRSs) with $O_\epsilon(\log n)$ samples, and (ii) a $(1/4 - \epsilon)$-selectable matroid OCRS with $O_\epsilon(\poly \log n)$ samples which carefully addresses an adaptivity challenge.

Based on joint work with Hu Fu, Pinyan Lu, Zhihao Tang, Hongxun Wu, Jinzhao Wu.

Time

2024-05-20  15:30 - 16:30   

Speaker

Qianfan Zhang, Princeton University

Room

Room 308