Abstract: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 ${\Omega}(1/k^2)$-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 ${\Omega}(1/k^2)$ fraction of the optimal weight. Using this lemma, we extend our ${\Omega}(1/k^2)$-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 ${\Omega}(\beta/k^2)$-competitive algorithm for $k$-growth systems, where $\beta$ 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.
From: Vasilis Livanos [view email]
[v1]
Thu, 6 Nov 2025 14:20:06 UTC (75 KB)
[v2]
Wed, 15 Jul 2026 06:54:03 UTC (82 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。