Improved algorithm selects valuable items faster in random order
A 3.7321-Competitive Algorithm for Matroid Secretary
Data Structures and AlgorithmsComputer Science and Game Theory
Summary
The matroid secretary problem involves picking the best set of items that arrive one by one in a random order, with decisions made instantly and permanently. The authors improve on a recent method by lowering the competitive ratio from 4 to about 3.732, meaning their approach selects better sets on average. They do this by cleverly modifying how part of the sample is kept flexible for exchanges, allowing precise calculation of when an item can be included. This leads to a more efficient algorithm that makes better selections while using a similar amount of computational effort.
What this means in practice
- •For online auction designers: Improve online selection mechanisms by better estimating the quality of incoming bids to pick high-value winners competitively.
- •For network schedulers: Design scheduling algorithms that select high-priority tasks arriving unpredictably without needing complete future knowledge.
A theory result. No direct application yet.
Authors
Hau Chan, Jianan Lin, Chenhao Wang
Abstract
The matroid secretary problem asks an online algorithm to select a high-weight independent set from elements arriving in uniformly random order, with immediate and irrevocable decisions. Singla (2026) recently gave a $4$-competitive algorithm for arbitrary matroids using only the number of elements and independence queries on already-arrived elements. Following his approach, we obtain an improved competitive ratio of $2+\sqrt3\approx3.7321$ in the same information model. Our algorithm accepts every element of a fixed canonical optimum with probability at least $2-\sqrt3$ and uses $O(n^2)$ independence queries. The algorithm modifies Singla's reversible reference process by retaining a randomly chosen part of the sample as a reserve whose membership in the reference greedy solution is not frozen. Balancing the remaining sample and post-sample elements preserves reversibility and allows an exact calculation of the probability that an exchange partner blocks a target element. The resulting guarantee has a direct analytic proof.