Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.04390 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909890607316992 |
|---|---|
| author | Bérczi, Kristóf Livanos, Vasilis Soto, José A. Verdugo, Victor |
| author_facet | Bérczi, Kristóf Livanos, Vasilis Soto, José A. Verdugo, Victor |
| contents | 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 the bipartite matching, matroid intersection, and random-order matroid secretary problems. In this model, elements form a bipartite graph between agents and items, and the objective is to select a matching that satisfies feasibility constraints on both sides, given by two independence systems.
We study the free-order setting, where the algorithm may adaptively choose the next element to reveal. For $k$-matroid intersection, we leverage a core lemma by (Feldman, Svensson and Zenklusen, 2022) to design an $Ω(1/k^2)$-competitive algorithm, extending known results for single matroids. Building on this, we identify the structural property underlying our approach and introduce $k$-growth systems. We establish a generalized core lemma for $k$-growth systems, showing that a suitably defined set of critical elements retains a $Ω(1/k^2)$ fraction of the optimal weight. Using this lemma, we extend our $Ω(1/k^2)$-competitive algorithm to $k$-growth systems for the edge-arrival model.
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 $Ω(β/k^2)$-competitive algorithm for $k$-growth systems, where $β$ denotes the competitiveness of a special type of order-oblivious algorithm for the item-side constraint. Finally, we relax the matching assumption and extend our results to the case of multiple item selection, where agents have individual independence systems coupled by a global item-side constraint. We obtain constant-competitive algorithms for fundamental cases such as partition matroids and $k$-matching constraints. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_04390 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Free-order secretary for two-sided independence systems Bérczi, Kristóf Livanos, Vasilis Soto, José A. Verdugo, Victor Data Structures and Algorithms 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 the bipartite matching, matroid intersection, and random-order matroid secretary problems. In this model, elements form a bipartite graph between agents and items, and the objective is to select a matching that satisfies feasibility constraints on both sides, given by two independence systems. We study the free-order setting, where the algorithm may adaptively choose the next element to reveal. For $k$-matroid intersection, we leverage a core lemma by (Feldman, Svensson and Zenklusen, 2022) to design an $Ω(1/k^2)$-competitive algorithm, extending known results for single matroids. Building on this, we identify the structural property underlying our approach and introduce $k$-growth systems. We establish a generalized core lemma for $k$-growth systems, showing that a suitably defined set of critical elements retains a $Ω(1/k^2)$ fraction of the optimal weight. Using this lemma, we extend our $Ω(1/k^2)$-competitive algorithm to $k$-growth systems for the edge-arrival model. 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 $Ω(β/k^2)$-competitive algorithm for $k$-growth systems, where $β$ denotes the competitiveness of a special type of order-oblivious algorithm for the item-side constraint. Finally, we relax the matching assumption and extend our results to the case of multiple item selection, where agents have individual independence systems coupled by a global item-side constraint. We obtain constant-competitive algorithms for fundamental cases such as partition matroids and $k$-matching constraints. |
| title | Free-order secretary for two-sided independence systems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.04390 |