Online Contention Resolution Schemes
Online Contention Resolution Schemes
复制标题
DOI：
10.1137/1.9781611974331.ch72
复制
发表时间：
2015-08
期刊：
影响因子：
--
通讯作者：
Moran Feldman;O. Svensson;R. Zenklusen
中科院分区：
文献类型：
--
作者：
Moran Feldman;O. Svensson;R. Zenklusen
我们介绍了一种针对在线优化问题而设计的新圆形技术，该技术与争夺分辨率方案有关，这是一种最初在suppodular函数最大化的背景下引入的技术。我们称之为在线争夺解决方案（OCRS）的舍入技术适用于许多在线选择问题，包括贝叶斯在线选择，忽略的已发布定价机制和随机探测模型。它允许处理广泛的约束，并具有离线争议解决方案的许多强大属性。特别是，可以将用于不同约束家族的OCR组合在一起，以获得与其交集的OCR。此外，我们可以在我们考虑的在线设置中近乎最大化subsodular功能。因此，我们为几个在线选择问题提供了一个广泛的适用框架，从可以处理的约束类型，可以处理的目标函数以及对对手强度的假设方面，它可以改善以前的方法。 。此外，我们解决了文献中的两个开放问题。也就是说，我们介绍了第一个恒定因素限制的遗漏，用于矩阵约束，以及第一种使用截止日期加权随机探测的恒定因子算法。
We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call online contention resolution schemes (OCRSs), is applicable to many online selection problems, including Bayesian online selection, oblivious posted pricing mechanisms, and stochastic probing models. It allows for handling a wide set of constraints, and shares many strong properties of offline contention resolution schemes. In particular, OCRSs for different constraint families can be combined to obtain an OCRS for their intersection. Moreover, we can approximately maximize submodular functions in the online settings we consider. We, thus, get a broadly applicable framework for several online selection problems, which improves on previous approaches in terms of the types of constraints that can be handled, the objective functions that can be dealt with, and the assumptions on the strength of the adversary. Furthermore, we resolve two open problems from the literature; namely, we present the first constant-factor constrained oblivious posted price mechanism for matroid constraints, and the first constant-factor algorithm for weighted stochastic probing with deadlines.