Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid

Richard Santiago, Ivan Sergeev, Rico Zenklusen

The Matroid Secretary Conjecture is a notorious open problem in online optimization. It claims the existence of an $O(1)$-competitive algorithm for the Matroid Secretary Problem (M…