Matroid secretary problem solved with new online selection method
The Matroid Secretary Conjecture is True
Data Structures and AlgorithmsComputer Science and Game Theory
Summary
The matroid secretary problem is about making the best possible choices online without knowing the future. The authors have found an algorithm that can pick the best elements with at least a 25% chance, even without knowing the whole setup ahead of time. This new method only needs to know how many elements will come and can check which chosen groups are independent, making it more flexible. This solves a long-standing challenge in computer science and optimization.
What this means in practice
- •For network schedulers: Schedule jobs arriving over time while ensuring resource constraints are met without full advance knowledge.
- •For supply chain planners: Select supply orders arriving sequentially to maximize value under combinatorial constraints.
A theory result. No direct application yet.
Authors
Sahil Singla
Abstract
We resolve the matroid secretary conjecture, giving an online algorithm that accepts each element of the offline optimum with probability at least $1/4$. The algorithm only needs the number of elements in advance and independence-oracle access to subsets of already-arrived elements; it does not need to know the matroid upfront.