Speaker: Vasilis Livanos
Centro de Modelamiento Matematico
Date: Tuesday, September 30, 2025 at 2:00 p.m. Santiago time

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.

Venue: John Von Neumann Seminar Room, CMM, Beauchef 851, North Tower, 7th Floor