Strong algorithms select elements from complex systems with better guarantees
On the Strong Matroid Secretary Conjecture and Beyond
Data Structures and Algorithms
Summary
Selecting the best items in a random order is a common problem, like hiring the best candidate without seeing all applicants at once. The authors study this problem in the setting of matroids, which model certain complex dependencies. They prove improved guarantees for choosing elements in many important matroid types, including well-known ones like graphs and networks. They also provide a new simple algorithm that performs well even with limited prior information.
What this means in practice
- •For network schedulers: Use improved selection algorithms to better manage resources subject to complex dependency constraints in real-time.
- •For online advertising teams: Implement algorithms that select ad placements more effectively when limited information arrives sequentially under combinatorial constraints.
Authors
Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Danny Mittal
Abstract
The strong matroid secretary conjecture asserts that every matroid admits a $1/e$-competitive secretary algorithm, matching the classical single-choice guarantee. We formulate a finite linear program whose value is the optimal ordinal competitive ratio of any fixed matroid; for all matroids of positive rank on seven elements and nearly all on eight, this value exceeds $1/e$. The same computations suggested that the optimal ratio is monotone under truncation of the matroid; we prove this for uniform matroids, where the ratio is strictly increasing in the rank, and refute it for a graphic matroid. Guided by this evidence, we prove the conjecture for every linear matroid, a class that includes graphic matroids, regular matroids, laminar matroids, and gammoids, giving a $1/e$-competitive ordinal secretary algorithm. The algorithm maintains bounds on the expected intersection dimension of the accepted span with every ambient subspace. Uncrossing and separation show that these bounds can be preserved while admitting each current greedy-basis element with a prescribed probability and the construction uses finite linear programs. For every matroid, we also give a single-sample prophet algorithm with competitive ratio $1/2$ in any fixed arrival order independent of the samples and values. Its output, including the selected values, has exactly the law of an independent fair thinning of an optimum from a fresh product draw. The algorithm uses $O(n^2)$ independence queries on $n$ elements. Both constants are tight in their respective models. We also give a self-contained black-box reduction that converts a single-sample prophet ratio $α$ into a secretary ratio $α^2/16$, preserving polynomial running time. Our single-sample algorithm consequently yields a $1/64$-competitive ordinal secretary algorithm for arbitrary matroids.