TY - GEN
T1 - Pairwise-Independent Contention Resolution
AU - Gupta, Anupam
AU - Hu, Jinqiao
AU - Kehne, Gregory
AU - Levin, Roie
N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
PY - 2024
Y1 - 2024
N2 - 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-ok(1))-selectable OCRS for uniform matroids of rank k, and Ω(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 et al. [14] 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 (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-ok(1))-selectable OCRS for uniform matroids of rank k, and Ω(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 et al. [14] showing that no ω(1/k)-selectable OCRS exists in the PI setting for general matroids of rank k.
KW - Contention Resolution
KW - Online Algorithms
KW - Prophet Inequalities
UR - https://www.scopus.com/pages/publications/85195137327
UR - https://www.scopus.com/pages/publications/85195137327#tab=citedBy
U2 - 10.1007/978-3-031-59835-7_15
DO - 10.1007/978-3-031-59835-7_15
M3 - Conference contribution
SN - 9783031598340
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 196
EP - 209
BT - Integer Programming and Combinatorial Optimization - 25th International Conference, IPCO 2024, Proceedings
A2 - Vygen, Jens
A2 - Byrka, Jarosław
PB - Springer Science and Business Media Deutschland GmbH
T2 - 25th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2024
Y2 - 3 July 2024 through 5 July 2024
ER -