Pairwise-Independent Contention Resolution

Anupam Gupta, Jinqiao Hu, Gregory Kehne, Roie Levin

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 25th International Conference, IPCO 2024, Proceedings
EditorsJens Vygen, Jarosław Byrka
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages14
ISBN (Print)9783031598340
StatePublished - 2024
Event25th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2024 - Wroclaw, Poland
Duration: Jul 3 2024Jul 5 2024

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14679 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference25th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2024


  • Contention Resolution
  • Online Algorithms
  • Prophet Inequalities

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Pairwise-Independent Contention Resolution'. Together they form a unique fingerprint.

Cite this