{"ID":2831901,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.06611","arxiv_id":"2512.06611","title":"The $k$-Fold Matroid Secretary Problem","abstract":"In the matroid secretary problem, elements $N := [n]$ of a matroid $\\mathcal{M} \\subseteq 2^N$ arrive in random order. When an element arrives, its weight is revealed and a choice must be made to accept or reject the element, subject to the constraint that the accepted set $S \\in \\mathcal{M}$. Kleinberg'05 gives a $(1-O(1/\\sqrt{k}))$-competitive algorithm when $\\mathcal{M}$ is a $k$-uniform matroid. We generalize their result, giving a $(1-O(\\sqrt{\\log(n)/k}))$-competitive algorithm when $\\mathcal{M}$ is a $k$-fold matroid union.","short_abstract":"In the matroid secretary problem, elements $N := [n]$ of a matroid $\\mathcal{M} \\subseteq 2^N$ arrive in random order. When an element arrives, its weight is revealed and a choice must be made to accept or reject the element, subject to the constraint that the accepted set $S \\in \\mathcal{M}$. Kleinberg'05 gives a $(1-...","url_abs":"https://arxiv.org/abs/2512.06611","url_pdf":"https://arxiv.org/pdf/2512.06611v1","authors":"[\"Rishi Gujjar\",\"Kevin Hua\",\"Robert Kleinberg\",\"Frederick V. Qiu\"]","published":"2025-12-07T01:03:07Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}