bipartite matching 1competitive analysis 1k-growth systems 1matroid secretary 1online optimization 1
From the 1 of 4 linked papers with an AI index.
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
The Multiple-Choice Matroid Secretary Problem
MatÃas Ortiz-Angel, José A. Soto
We introduce and study the multiple-choice matroid secretary problem, denoted -MSP. For rank-one matroids and , it reduces to the classical secretary problem wit…
cs.DS2026
Free-Order Online Selection for k-Systems
Kristóf Bérczi, Vasilis Livanos, José A. Soto +1
The paper studies online selection problems on bipartite graphs with combinatorial constraints, introducing k‑growth systems and providing Ω(1/k²)-competitive algorithms for free‑o…
cs.DS2025
Matroid Secretary via Labeling Schemes
Kristóf Bérczi, Vasilis Livanos, José Soto +1
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 el…