CS Peer Talk | Sample-Based Matroid Prophet Inequalities

报告人：Jinzhao Wu, Yale University

时间：3月25日（星期一）2:00pm

地点：静园五院204

Host：陈炤桦，图灵班2017级

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.

Four years ago, we developed an algorithm to address the matroid prophet inequalities problem using  samples. Unfortunately, this algorithm was shown to be incorrect. In this work, we finally are able to give a  -competitive matroid prophet inequality with only  samples. Our algorithm consists of two parts: (i) a novel quantile-based reduction from matroid prophet inequalities to online contention resolution schemes (OCRSs) with  samples, and (ii) a  -selectable matroid OCRS with   samples which carefully addresses an adaptivity challenge.

Jinzhao Wu is a second-year Ph.D. student in Computer Science at Yale University, where he is advised by Prof. Yang Cai. He has a broad interest in theoretical computer science, with a particular focus on algorithmic game theory and computational problems arising from the field of economics.

北京大学图灵班科研活动委员会