Simple and Almost Non-Adaptive \(\frac{1}{2}\)-Approximation for Matroid Prophet Inequalities

Sina Kalantarzadeh, Kanstantin Pashkovich

Prophet inequalities are a fundamental model for online decision-making under uncertainty. For matroid constraints, Kleinberg and Weinberg gave a tight $\frac{1}{2}$-approximation…