Sample-Based Matroid Prophet Inequalities
<|reference_start|>Sample-Based Matroid Prophet Inequalities: 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 $(\frac14 - \varepsilon)$-competitive matroid prophet inequality with only $O_\varepsilon(\mathrm{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_\varepsilon(\log n)$ samples, and (ii) a $(\frac14 - \varepsilon)$-selectable matroid OCRS with $O_\varepsilon(\mathrm{poly} \log n)$ samples which carefully addresses an adaptivity challenge.<|reference_end|>
@article{fu2024sample-based,
    title={Sample-Based Matroid Prophet Inequalities},
    author={Hu Fu, Pinyan Lu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, Qianfan
  Zhang},
    journal={arXiv preprint arXiv:2406.12799},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.12799},
    primaryClass={cs.DS}
}