Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities
Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities
复制标题
通过事前先知不等式的最优在线争用解决方案
DOI：
10.4230/lipics.esa.2018.57
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Sahil Singla
中科院分区：
文献类型：
--
作者：
Euiwoong Lee;Sahil Singla
在线竞争解决方案（OCRS）是由Feldman，Svensson和Zenklusen提出的，作为一种通用的技术，以在线方式在拟阵多面体中舍入分数解。它在几个存在承诺约束的随机组合问题中得到了应用：在看到随机元素的值时，算法必须立即且不可撤销地决定是否选择它，同时始终保持拟阵中的独立集。虽然OCRS直接导致先知不平等，但这些先知不平等并不是最优的。我们能用预言不等式来设计最优的OCRS吗？
我们设计的第一个最佳的$1/2$-OCRS拟阵减少的问题，设计一个拟阵先知不等式，我们比较强的基准的事前放松。我们还介绍和设计最佳的$（1-1/e）$-随机顺序CRS的拟阵，这是类似的OCRS，但到达随机均匀选择。
Online contention resolution schemes (OCRSs) were proposed by Feldman, Svensson, and Zenklusen as a generic technique to round a fractional solution in the matroid polytope in an online fashion. It has found applications in several stochastic combinatorial problems where there is a commitment constraint: on seeing the value of a stochastic element, the algorithm has to immediately and irrevocably decide whether to select it while always maintaining an independent set in the matroid. Although OCRSs immediately lead to prophet inequalities, these prophet inequalities are not optimal. Can we instead use prophet inequalities to design optimal OCRSs?
We design the first optimal $1/2$-OCRS for matroids by reducing the problem to designing a matroid prophet inequality where we compare to the stronger benchmark of an ex-ante relaxation. We also introduce and design optimal $(1-1/e)$-random order CRSs for matroids, which are similar to OCRSs but the arrival is chosen uniformly at random.
DOI：
10.1007/978-3-662-48350-3_42
发表时间：
2015-07
期刊：
ArXiv
影响因子：
--
作者：
H. Esfandiari;M. Hajiaghayi;Vahid Liaghat;M. Monemizadeh
通讯作者：
H. Esfandiari;M. Hajiaghayi;Vahid Liaghat;M. Monemizadeh