Pairwise-Independent Contention Resolution
<|reference_start|>Pairwise-Independent Contention Resolution: We study online contention resolution schemes (OCRSs) 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-o_k(1))$-selectable OCRS for uniform matroids of rank $k$, and $\Omega(1)$-selectable OCRSs 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, Kalayci, and Patel (STOC '24) showing that no $\omega(1/k)$-selectable OCRS exists in the PI setting for general matroids of rank $k$.<|reference_end|>
@article{gupta2024pairwise-independent,
    title={Pairwise-Independent Contention Resolution},
    author={Anupam Gupta, Jinqiao Hu, Gregory Kehne, Roie Levin},
    journal={arXiv preprint arXiv:2406.15876},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.15876},
    primaryClass={cs.DS}
}