Type: Book-Chapter
Publication Date: 2022-01-01
Citations: 2
DOI: https://doi.org/10.1137/1.9781611977066.20
Previous chapter Next chapter Full AccessProceedings Symposium on Simplicity in Algorithms (SOSA)Oblivious Online Contention Resolution SchemesHu Fu, Pinyan Lu, Zhihao Gavin Tang, Abner Turkieltaub, Hongxun Wu, Jinzhao Wu, and Qianfan ZhangHu Fu, Pinyan Lu, Zhihao Gavin Tang, Abner Turkieltaub, Hongxun Wu, Jinzhao Wu, and Qianfan Zhangpp.268 - 278Chapter DOI:https://doi.org/10.1137/1.9781611977066.20PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract Contention resolution schemes (CRSs) are powerful tools for obtaining "ex post feasible" solutions from candidates that are drawn from "ex ante feasible" distributions. Online contention resolution schemes (OCRSs), the online version, have found myriad applications in Bayesian and stochastic problems, such as prophet inequalities and stochastic probing. When the ex ante distribution is unknown, it was unknown whether good CRSs/OCRSs exist with no sample (in which case the scheme is oblivious) or few samples from the distribution. In this work, we give a simple -selectable oblivious single item OCRS by mixing two simple schemes evenly, and show, via a Ramsey theory argument, that it is optimal. On the negative side, we show that no CRS or OCRS with O(1) samples can be Ω(1)-balanced/selectable (i.e., preserve every active candidate with a constant probability) for graphic or transversal matroids. Previous chapter Next chapter RelatedDetails Published:2022eISBN:978-1-61197-706-6 https://doi.org/10.1137/1.9781611977066Book Series Name:ProceedingsBook Code:SOSA22Book Pages:v + 320