Secretary Problems and Combinatorial Optimal Stopping.

Abstract: Secretary problems constitute a classical setting of online decision-making, where discrete elements arrive in uniformly random order, reveal their weight, and must be accepted or rejected irrevocably, with the aim of maximizing a given function over the selected set. In the most general form of the problem, we are given a combinatorial feasibility constraint (e.g. a matroid) and the selected set has to be feasible with respect to that constraint. In such problems, the objective is to design algorithms which guarantee a multiplicative factor approximation with respect to the optimal feasible set if we knew the weights of the elements in advance. By far the most important open problem in this area is the Matroid Secretary conjecture, which states that there exists a constant-factor approximation algorithm for every given matroid, and has been open for almost two decades now.

In this talk, I will introduce secretary problems, describe some standard ideas and approaches for them, as well as present what is  probably my favourite algorithm of all time: Korula and Pal’s  1/(2e)-approximate algorithm for the graphic matroid setting (i.e.  selecting an acyclic set of edges in an undirected graph where the  weights of the edges is revealed online in uniformly random order).  Later on, if time permits, I will present some recent progress on  algorithms for the general Matroid Secretary conjecture. This talk will  be partly based on joint work with Kristóf Bérczi, José Soto and Victor  Verdugo that appeared in IPCO 2025.

Posted on Sep 29, 2025 in Seminars, SIPo (Seminario de Investigadores Postdoctorales)