Oblivious Online Contention Resolution Schemes
231
Microsoft Research334 тыс
Следующее
12.12.22 – 72830:03Популярные
129 дней – 1 15059:38
02.11.23 – 5811:07:21Опубликовано 12 декабря 2022, 20:34
2022 Data-driven Optimization Workshop: Oblivious Online Contention Resolution Schemes
Speaker: Hu Fu, Shanghai University of Finance and Economics
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 1/e-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.
Speaker: Hu Fu, Shanghai University of Finance and Economics
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 1/e-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.
Свежие видео
17 часов – 5523:56
1 день – 2 8459:24
3 дня – 2 9150:15
9 дней – 199 91112:11
10 дней – 376 4824:25
10 дней – 24 1015:04Случайные видео
92 дня – 5020:03
03.07.23 – 8 1668:39
14.06.23 – 1 626 09018:49
18.12.22 – 6 4345:41
09.10.22 – 10 9134:19
19.11.20 – 38 6784:06
18 часов – 42 13210:40
6 дней – 654 7976:21
8 дней – 609 8546:40
10 дней – 1 4151:48
12 дней – 12 8932:29
12 дней – 6 8640:22
4 часа – 2 99341:38
16 часов – 25 92411:42