Prophet Secretary for Matroids and XOS Valuations: A Separation at 1-1/e and a 0.6767 Guarantee for I.I.D. Weights

arXiv:2611.06891 · cs.DS, cs.GT · Submitted 2026-11-04 · Read on arXiv

cs.DS, cs.GT

Submitted: 2026-11-04

Updated: 2026-11-06

Code: https://github.com/hajiaghayi/Matroid-Prophet-Secretary-XOS

Terminology

Sources

Related papers