NeFut Logo NeFut
中 Admin Login

[CS.DS] As Easy as Rank One: Optimal Algorithms for Matroid Secretary and Single‑Sample Matroid Prophet

Published at: 2026-11-09 22:00 Last updated: 2026-11-12 00:51
#algorithm #optimization #Math

We settle the strong form of the matroid secretary conjecture and the single‑sample matroid prophet inequality, achieving competitive ratios $e$ and $2$ respectively, both optimal even for rank‑one matroids. For the secretary problem, an ordinal algorithm accepts each element of the canonical optimum independently with probability $1/e$, requires only the total number of elements in advance, and uses an expected polynomial number of independence queries on arriving elements. The single‑sample prophet algorithm draws one sample per independent value distribution, performs $O(n^2)$ independence queries on a known $n$‑element matroid, and works for any arrival order that is fixed independently of the samples, values, and algorithmic randomness. The selected elements and their values have exactly the joint distribution obtained by independently retaining each element‑value pair in the canonical optimum of a fresh product draw with probability $1/2$. The main algorithms maintain a reference state whose greedy solution always contains every accepted element; updates, even after rejections, preserve exact distributional invariants. A short reversible‑update argument yields a $4$‑probability‑competitive secretary algorithm, resolving the original conjecture, while a related invariant gives the optimal single‑sample prophet inequality. For the secretary problem we characterize the distributions achievable by ordinal algorithms via a finite polytope, then use a continuous‑time formulation to design an accepted‑set distribution achieving the optimal ratio $e$ and implement it efficiently. Guarantees for matroid intersections are also obtained.\n\nReview: This work establishes new optimal benchmarks for matroid optimization, delivering the first strong‑form optimal competitive ratios and introducing a unified invariance framework that will likely influence future algorithmic developments in the area.

Original Source: https://arxiv.org/abs/2611.08869

[h] Back to Home