Matroid Secretary via Labeling Schemes

Bérczi, Kristóf and Livanos, Vasilis and Soto, José A. and Verdugo, Victor (2025) Matroid Secretary via Labeling Schemes. In: Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science (15620). Springer Nature Switzerland, Cham, pp. 128-141. ISBN 9783031931116; 9783031931123

Preview

Text 2411.12069v2.pdf - Draft Version Available under License Creative Commons Attribution. Download (643kB) | Preview

Abstract

The matroid secretary problem (MSP) is one of the most prominent settings for online resource allocation and optimal stopping. A decision-maker is presented with a ground set of elements E revealed sequentially and in random order. Upon arrival, an irrevocable decision is made in a take-it-or-leave-it fashion, subject to a feasibility constraint on the set of selected elements captured by a matroid defined over E. The decision-maker only has ordinal access to compare the elements, and the goal is to design an algorithm that selects every element of the optimal basis with probability at least α (i.e., α-probability-competitive). While the existence of a constant probability-competitive algorithm for MSP remains a major open question, simple greedy policies are at the core of state-of-the-art algorithms for several matroid classes. We introduce a flexible and general algorithmic framework to analyze greedy-like algorithms for MSP based on constructing a language associated with the matroid. Via this language, we establish a lower bound on the probability-competitiveness of the algorithm by studying a corresponding Poisson point process that governs the words’ distribution in the language. Using our framework, we break the state-of-the-art guarantee for laminar matroids by settling the probability-competitiveness of the greedy-improving algorithm to be exactly 1 − ln(2) ≈ 0.3068. We also showcase the capabilities of our framework in graphic matroids, to show a probabilitycompetitiveness of 0.2693 for simple graphs and 0.2504 for general graphs.

Actions (login required)

Edit Item