Our paper on Matroid products via submodular coupling has been accepted to the 57th Annual ACM Symposium on Theory of Computing (STOC 2025)! In this paper, inspired by the concept of coupling in probability theory, we introduce the notion of coupling for matroids – or, more generally, for submodular set functions. This operation can be…
Our paper on Matroid secretary via labeling schemes was accepted at IPCO! In this work, we introduce an algorithmic framework for analyzing greedy-like algorithms for the matroid secretary problem by constructing a language associated with the matroid. Using this approach, we improve the state-of-the-art guarantee for laminar matroids by determining the exact probability-competitiveness of the…
The research group wrapped up 2024 with some great achievements. Tibor Jordán was awarded the prestigious Szele Tibor Memorial Medal in recognition of his outstanding work in mathematics and his support for young researchers. Tamás Schwarcz received the Grünwald Géza Prize for his exceptional contributions to pure mathematics and successfully defended his doctoral thesis. Starting…
The famous Ryser – Brualdi – Stein conjecture asserts that every $n\times n$ Latin square contains a partial transversal of size $n-1$. Since its appearance, the conjecture has attracted significant interest, leading to several generalizations. One of the most notable extensions is to matroid intersection given by Aharoni, Kotlar, and Ziv, focusing on the existence…
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…