Nearly Tight Sample Complexity for Matroid Online Contention Resolution

Moran Feldman, Ola Svensson, Rico Zenklusen

Due to their numerous applications, in particular in Mechanism Design, Prophet Inequalities have experienced a surge of interest. They describe competitive ratios for basic stoppin…