Matroid Secretary is Equivalent to Contention Resolution
summary
Main claim: the matroid secretary conjecture is equivalent (up to constant factors) to the statement that offline contention resolution and online random‑order contention resolution are equally powerful for all uncontentious distributions (the improving‑elements distributions are 1/2‑uncontentious). Proof tools: a polyhedral characterization of contentious distributions (from ICALP 2020), reduction matroid secretary → prophet‑secretary → labeled contention resolution → unlabeled CR via an expanded matroid with many label‑copies, and min–max duality; constants are preserved throughout so a constant CR yields a constant competitive ratio.
AI-written summary · about