Laminar Matroid Secretary: Greedy Strikes Back
share
We show that a simple greedy algorithm is 4.75 probability-competitive for the Laminar Matroid Secretary Problem, improving the 3√(3)≈ 5.17-competitive algorithm based on the forbidden sets technique (Soto, Turkieltaub, and Verdugo, 2018).
READ FULL TEXT