2025/11/06 by Kristóf Bérczi, Vasilis Livanos, Bérczi, Kristóf +5
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Applications #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2511.04390
openalex publication_date 2025/11/06 · openalex created_date 2025/11/08 · openalex updated_date 2026/07/28
The Matroid Secretary Problem is a central question in online optimization, modeling sequential decision-making under combinatorial constraints. We introduce a bipartite graph framework that unifies and extends several known formulations, including bipartite matching, matroid intersection, and matroid secretary problems. In this model, agents and items form a bipartite graph, and the objective is to select a matching that satisfies independence constraints on both sides. We first study the free-order setting under edge-arrivals. For k-matroid intersection, we leverage a core lemma by [FSZ, 2022] to design an Ω(1/k2)-competitive algorithm, extending known results for single matroids. Building on this, we introduce k-growth systems -- a new class of independence systems that lie properly between k-matchoids and k-extendible systems and may be of independent combinatorial interest. We establish a generalized core lemma for k-growth systems, showing that a suitably defined set of critical elements retains a Ω(1/k2) fraction of the optimal weight. Using this lemma, we extend our Ω(1/k2)-competitive algorithm to k-growth systems. We then study the agent-arrival model, which presents unique challenges to our framework. We extend the core lemma to this model and then apply it to obtain an Ω(β/k2)-competitive algorithm for k-growth systems, where β denotes the competitiveness of an appropriate type of order-oblivious algorithm for the item-side constraint. Finally, we extend our results to the case of multiple item selection, and obtain constant-competitive algorithms for fundamental cases such as partition matroids and k-matching constraints. We also study the closure properties and structural role and of k-growth systems within the hierarchy of k-systems.