{"ID":22918755,"CreatedAt":"2026-09-17T01:02:08.507062015Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.17782","arxiv_id":"2609.17782","title":"A 3.7321-Competitive Algorithm for Matroid Secretary","abstract":"The matroid secretary problem asks an online algorithm to select a high-weight independent set from elements arriving in uniformly random order, with immediate and irrevocable decisions. Singla (2026) recently gave a $4$-competitive algorithm for arbitrary matroids using only the number of elements and independence queries on already-arrived elements. Following his approach, we obtain an improved competitive ratio of $2+\\sqrt3\\approx3.7321$ in the same information model. Our algorithm accepts every element of a fixed canonical optimum with probability at least $2-\\sqrt3$ and uses $O(n^2)$ independence queries. The algorithm modifies Singla's reversible reference process by retaining a randomly chosen part of the sample as a reserve whose membership in the reference greedy solution is not frozen. Balancing the remaining sample and post-sample elements preserves reversibility and allows an exact calculation of the probability that an exchange partner blocks a target element. The resulting guarantee has a direct analytic proof.","short_abstract":"The matroid secretary problem asks an online algorithm to select a high-weight independent set from elements arriving in uniformly random order, with immediate and irrevocable decisions. Singla (2026) recently gave a $4$-competitive algorithm for arbitrary matroids using only the number of elements and independence que...","url_abs":"https://arxiv.org/abs/2609.17782","url_pdf":"https://arxiv.org/pdf/2609.17782v1","authors":"[\"Hau Chan\",\"Jianan Lin\",\"Chenhao Wang\"]","published":"2026-09-15T19:46:04Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.GT\"]","methods":"[]","has_code":false}