Full Name
Jinzhao Wu
Primary Department, Unit, or Institute
Computer Science
University/Company
Yale
Talk Title
Sample-based Matroid Prophet Inequalities
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-eps)-competitive matroid prophet inequality with only O(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(log n) samples, and (ii) a (1/4-eps)-selectable matroid OCRS with O(poly log n)samples which carefully addresses an adaptivity challenge.
In this work, we give a (1/4-eps)-competitive matroid prophet inequality with only O(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(log n) samples, and (ii) a (1/4-eps)-selectable matroid OCRS with O(poly log n)samples which carefully addresses an adaptivity challenge.