Open Collections

Ramezani, Iliad

University of British Columbia

We investigate the problem of designing (preferably optimal) online contention resolution schemes (OCRSs). They are a powerful framework for optimization under various combinatorial constraints such as matroids, matchings, knapsacks and their intersections. OCRSs immediately imply prophet inequalities in Bayesian online selection problem. They also have other important applications such as stochastic probing and oblivious posted price mechanisms. We present several novel OCRSs which improve the current state-of-the-art algorithms. We design an optimal 0.5-selectable OCRS over matroids with rank 2, and another optimal 0.5-selectable OCRS over transversal matroids. Previously the best result applicable to these types of matroids was a 0.25-selectable OCRS. Furthermore, we design a 1/(k+1)-selectable OCRS over matchings in k-partite hypergraphs.

Text

2021-09-10

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/79698

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/