3 papers
cs.DS2024
Pairwise-Independent Contention Resolution
Anupam Gupta, Jinqiao Hu, Gregory Kehne +1
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-i…
cs.GT2024
A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization
Shuchi Chawla, Dimitris Christou, Trung Dang +3
We study multi-buyer multi-item sequential item pricing mechanisms for revenue maximization with the goal of approximating a natural fractional relaxation -- the ex ante optimal re…
cs.DS2023
Set Covering with Our Eyes Wide Shut
Anupam Gupta, Gregory Kehne, Roie Levin
In the stochastic set cover problem (Grandoni et al., FOCS '08), we are given a collection of sets over a universe of size , and a distribution $…