2026-07-23T04:49:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22632 2026-04-17T05:31:37Z ddc:004 open_access

A Bicriterion Concentration Inequality and Prophet Inequalities for k-Fold Matroid Unions Alon, Noga Gravin, Nick Pollner, Tristan Rubinstein, Aviad Wang, Hongao Weinberg, S. Matthew Zhang, Qianfan Prophet Inequalities Online Contention Resolution Schemes Concentration Inequalities We investigate prophet inequalities with competitive ratios approaching 1, seeking to generalize k-uniform matroids. We first show that large girth does not suffice: for all k, there exists a matroid of girth ≥ k and a prophet inequality instance on that matroid whose optimal competitive ratio is 1/2. Next, we show k-fold matroid unions do suffice: we provide a prophet inequality with competitive ratio 1-O(√{(log k)/k}) for any k-fold matroid union. Our prophet inequality follows from an online contention resolution scheme. The key technical ingredient in our online contention resolution scheme is a novel bicriterion concentration inequality for arbitrary monotone 1-Lipschitz functions over independent items which may be of independent interest. Applied to our particular setting, our bicriterion concentration inequality yields "Chernoff-strength" concentration for a 1-Lipschitz function that is not (approximately) self-bounding. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noga Alon and Nick Gravin and Tristan Pollner and Aviad Rubinstein and Hongao Wang and S. Matthew Weinberg and Qianfan Zhang 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.4 urn:nbn:de:0030-drops-226329 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.4 eng https://creativecommons.org/licenses/by/4.0/legalcode