{"id":5871,"date":"2025-05-19T04:14:25","date_gmt":"2025-05-19T08:14:25","guid":{"rendered":"http:\/\/matroidunion.org\/?p=5871"},"modified":"2025-05-26T16:37:32","modified_gmt":"2025-05-26T20:37:32","slug":"greedy-strikes-back-a-4-75-competitive-algorithm-for-the-laminar-matroid-secretary-problem","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=5871","title":{"rendered":"Greedy strikes back: A 4.75-competitive algorithm for the laminar matroid secretary problem"},"content":{"rendered":"\n

This is a guest post by Zahra Parsaeian<\/a>. This post is a follow-up to Tony Huynh\u2019s 2015 blog post<\/a> of the matroid secretary problem, focusing on the special case of laminar matroids. Zahra highlights the last decade’s steady progress in this special case and outlines the recent greedy algorithm that brings the competitive ratio down to 4.75.<\/em><\/p>\n\n\n\n

From Secretaries to Laminar Matroids<\/h2>\n\n\n\n

The classical secretary problem asks for a strategy that hires (with high probability) the best of $n$ applicants who appear in uniformly random order. The well-known threshold strategy\u2014observe the first $n\/e$ applicants, then pick the first candidate better than all previous ones\u2014achieves a competitive ratio of $e$.<\/p>\n\n\n\n

The matroid secretary problem (MSP), introduced by Babaioff, Immorlica & Kleinberg (2007)<\/a>, generalises this set-selection game: instead of choosing a single element, we must pick an independent<\/em> set of elements in an (unknown) weighted matroid that arrive online. The grand conjecture is that every matroid admits an $O(1)$-competitive algorithm.<\/p>\n\n\n\n

A particularly structured\u2014and surprisingly rich\u2014family of matroids is the laminar matroids. Here the ground set $E$ is organised by a laminar family<\/a> $\\mathcal{F}$ (any two sets are either disjoint or nested), and each $B \\in \\mathcal{F}$ comes with a capacity $c(B)$; a subset $S \\subseteq E$ is independent if $|S \\cap B| \\leq c(B)$ for every $B$. Partition matroids are the simplest laminar matroids, but many “hierarchical quota” constraints in practice are laminar as well.<\/p>\n\n\n\n

Why single them out? Laminar matroids already capture the core difficulty of MSP while admitting extra structure that can be exploited algorithmically.<\/p>\n\n\n\n

A Decade of Improving Constants<\/h2>\n\n\n\n

Tony\u2019s 2015 survey listed Im & Wang\u2019s first constant-competitive algorithm (competitive ratio $\\approx 5333.33$). Since then the record book has been rewritten multiple times:<\/p>\n\n\n\n

Year<\/strong><\/td>Authors<\/strong><\/td>Technique<\/strong><\/td>Competitive ratio<\/strong><\/td><\/tr>
2011<\/td>Im & Wang<\/a><\/td>Reduction to partition + “sample and price”<\/td> $16000\/3 \\approx 5333.33$ <\/td><\/tr>
2013<\/td>Jaillet, Soto & Zenklusen<\/a><\/td>Improved reduction<\/td>$\\sqrt{3e} \\approx 14.12$<\/td><\/tr>
2016<\/td>Ma, Tang & Wang<\/a><\/td>Simulated greedy<\/td>9.6<\/td><\/tr>
2018<\/td>Soto, Turkieltaub & Verdugo<\/a><\/td>Forbidden sets<\/td>$3\\sqrt{3} \\approx 5.196$<\/td><\/tr>
2024<\/td>Huang, Parsaeian & Zhu<\/a><\/td>Plain greedy<\/td>4.75<\/td><\/tr>
2024<\/td>B\u00e9rczi, Livanos, Soto & Verdugo<\/a><\/td>Labeling scheme (tight)<\/td>$1\/(1 – \\ln 2) \\approx 3.257$<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Progress has come from increasingly delicate analyses, often accompanied by algorithmic complexity. The latest result is a counter-trend: a simpler algorithm with a better constant.<\/p>\n\n\n\n

Greedy\u2014But With Better Timing<\/h2>\n\n\n\n

Before we describe the algorithm, recall the standard arrival model: each element independently receives a uniformly random arrival time in $[0,1]$, yielding a random order of appearance that our online algorithm must process.<\/p>\n\n\n\n

Our algorithm really is the textbook greedy rule, decorated with a single time threshold $t_0$.<\/p>\n\n\n\n