TY - JOUR
T1 - Pairwise-independent contention resolution
AU - Gupta, Anupam
AU - Hu, Jinqiao
AU - Kehne, Gregory
AU - Levin, Roie
N1 - Publisher Copyright:
© The Author(s) 2025.
PY - 2025
Y1 - 2025
N2 - We study online contention resolution schemes (OCRSes) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a pairwise-independent (PI) distribution, we show a (1-ok(1))-selectable OCRS for uniform matroids of rank k, and Ω(1)-selectable OCRSes for laminar, graphic, cographic, transversal, and regular matroids. These imply prophet inequalities with the same ratios when the set of values is drawn according to a PI distribution. Our results complement recent work of Dughmi et al. [2] showing that no ω(1/k)-selectable OCRS exists in the PI setting for general matroids of rank k.
AB - We study online contention resolution schemes (OCRSes) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a pairwise-independent (PI) distribution, we show a (1-ok(1))-selectable OCRS for uniform matroids of rank k, and Ω(1)-selectable OCRSes for laminar, graphic, cographic, transversal, and regular matroids. These imply prophet inequalities with the same ratios when the set of values is drawn according to a PI distribution. Our results complement recent work of Dughmi et al. [2] showing that no ω(1/k)-selectable OCRS exists in the PI setting for general matroids of rank k.
KW - Combinatorial Optimization
KW - Limited Independence
KW - Matroids
KW - Online Algorithms
KW - Prophet Inequalities
UR - https://www.scopus.com/pages/publications/105010655169
U2 - 10.1007/s10107-025-02253-w
DO - 10.1007/s10107-025-02253-w
M3 - Article
AN - SCOPUS:105010655169
SN - 0025-5610
JO - Mathematical Programming
JF - Mathematical Programming
ER -