Dec 7, 2023

Matroid secretary problem with random assignment and almost no prior information

Date: December 7, 2023 | 11:00 am – 12:15 pm
Speaker: Ivan Sergeev, ETH Zurich
Location: Moonstone Bldg / Ground floor / Seminar Room C (I24.EG.030c)
Language: English

The matroid secretary problem (MSP) is an online selection problem where elements of a weighted matroid are revealed one by one, and the goal is to pick an independent set of as large weight as possible. This setting is motivated by applications in online mechanism design and generalizes the classical secretary problem. It was conjectured that, similar to the classical secretary, there exists an algorithm that is constant-competitive for any matroid. Despite the long line of work dedicated to the problem, so far constant competitive ratio has been attained only for certain classes of matroids and for some variations of MSP. One example is the random assignment model (RAMSP), where an adversary fixes a number of weights equal to the cardinality of the matroid, which then get randomly assigned to the elements of the ground set. However, the two known constant-competitive algorithms for this setting, one by Soto (2013) and the other by Oveis Gharan and Vondrák (2013), crucially rely on knowing the full matroid upfront. Lifting this requirement was left as an open question by the aforementioned authors, as there are good arguments for why such assumptions on prior information should be avoided. In this talk, I will present a constant-competitive algorithm for RAMSP that only needs to know the cardinality of the underlying matroid upfront, making RAMSP the first known MSP variant admitting such an algorithm.