Metraipolis › archive › dc_1fe8a86b58d4
Prophet Inequalities and Online Contention Resolution for Matchoids — arXiv:2609.20939
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.20939
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T02:45:56.475Z
- SHA-256 of the archived text
163fd4c95538584319d8eacfc67eb561195c8424034fd12ebc3ee201d741b7e0- Stable URL of this page
https://metraipolis.com/documento/dc_1fe8a86b58d4
How to cite
Prophet Inequalities and Online Contention Resolution for Matchoids — arXiv:2609.20939 — arXiv (en), https://arxiv.org/abs/2609.20939 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1fe8a86b58d4 (Metraipolis archive dc_1fe8a86b58d4, sha256 163fd4c95538584319d8eacfc67eb561195c8424034fd12ebc3ee201d741b7e0)
BibTeX
@misc{dc1fe8a86b58d4,
title = {Prophet Inequalities and Online Contention Resolution for Matchoids — arXiv:2609.20939},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.20939},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1fe8a86b58d4; sha256 163fd4c95538584319d8eacfc67eb561195c8424034fd12ebc3ee201d741b7e0},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20939. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In the classical prophet inequality, an algorithm observes a sequence of random variables with known distributions in an online fashion, and it must select one of the random variables with the goal of maximizing the expected value of its selection. The performance of the algorithm is compared to an \textit{omniscient prophet} who observes all of the random variables before having to make its selection. Combinatorial extensions of the classical prophet inequality in which the algorithm gets to pick a subset of the random variables (constrained to belong to some family of feasible sets) have been studied extensively. We study prophet inequalities with a $k$-matchoid constraint (a common generalization of a $k$-matroid intersection constraint and a $k$-bounded hypergraph matching constraint) in two common online arrival models. We give guarantees with respect to the \textit{ex-ante} fractional relaxation of the omniscient prophet, obtaining an ex-ante competitive ratio of $\frac{1}{k+1}$ in the adversarial order case, and $\frac{1-e^{-k}}{k}$ in the random order case. Using the duality framework of Lee and Singla \cite{Lee2018}, this also yields online contention resolution schemes in these settings. Our adversarial-order prophet inequality can be viewed as a generalization of a recent $\frac12$-competitive matroid prophet inequality by Kalantarzadeh and Pashkovich, 2026. This generalization introduces a new framework: coordinated weighted principal partitions across multiple matroids. Our random-order prophet inequality is a generalization of the $k=1$ matroid case of Lee and Singla, 2018. The two results improve previously known competitive ratios for $k$-matroid intersection, which were $\frac{1}{(e+o(1))k}$ and $\frac{1}{k+1}$, respectively.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-21 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.20939 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T02:29:42.994Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).