MathDB

Strong Secretary Conjecture for linear matroids

For every matroid M=(E,I)M=(E,\mathcal{I}) and every nonnegative weight function w:E→R≥0w:E\to\mathbb{R}_{\ge 0}, when the elements of EE arrive in a uniformly random order and their weights are revealed upon arrival, there exists an online algorithm that always selects an independent set I∈II\in\mathcal{I} and satisfies E[w(I)]≥1e OPT⁡(M,w)\mathbb{E}[w(I)]\ge \frac{1}{e}\,\operatorname{OPT}(M,w), where OPT⁡(M,w)=max⁡{w(J):J∈I}\operatorname{OPT}(M,w)=\max\{w(J):J\in\mathcal{I}\}.

References

Primary source

arXiv

Additional references

combinatorial-optimizationmatroid-theoryonline-algorithms
Posted · edited

Progress summary

Refreshed
Claimed solved

Two September 2026 manuscripts claim to prove the conjecture, but neither proof has been independently checked.

The Strong Secretary Conjecture seeks a 1/e1/e-competitive online selection algorithm for linear matroids, including settings where the representation arrives online. A proof would settle this central case of the matroid secretary problem.

Known results

  • A November 2024 survey described the conjecture as proved only for uniform, partition, and transversal matroids, with linear matroids unresolved.

September 16–17, 2026 claimed proofs

On September 16, 2026, Abdi, Banihashem, Hajiaghayi, and Mittal claimed a 1/e1/e ordinal-secretary guarantee for every linear matroid. On September 17, 2026, Bérczi, Dughmi, Livanos, Soto, and Verdugo made a concurrent claim covering both known matroids and online finite-field representations; they say ChatGPT-6 Astra produced the proof in a September 15 conversation. The manuscripts disclose that the claims are essentially identical, so they are not independent confirmations.

Current status (as of September 2026): Two concurrent manuscripts claim the conjecture is proved with guarantee 1/e1/e, but both proofs remain unrefereed and independently unverified.

Sources

Solutions 0

No solutions have been posted yet.