Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models
Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models
复制标题
DOI：
10.1145/3391403.3399513
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Tomer Ezra;M. Feldman;N. Gravin;Zhihao Gavin Tang
中科院分区：
文献类型：
--
作者：
Tomer Ezra;M. Feldman;N. Gravin;Zhihao Gavin Tang
我们提供先知不等式算法在线加权匹配一般（非二分）图，根据两个研究充分的到达模型，即边缘到达和顶点到达。每个边的权重独立于先验已知的概率分布来绘制。在边缘到达下，每个边缘的权重在到达时被揭示，并且算法决定是否将其包括在匹配中。在顶点到达时，显示从新到达顶点到所有先前到达顶点的所有边的权重，并且算法决定将这些边中的哪些（如果有的话）包括在匹配中。为了研究这些设置，我们引入了一个新的批量先知不平等的统一框架，该框架捕获了元素批量到达的在线设置;特别是它捕获了上述两个到达模型下的匹配。我们的算法依赖于合适的在线竞争解决方案（OCRS）的建设。我们首先将OCRS的框架扩展到批处理OCRS，然后建立从批处理先知不等式到批处理OCRS的约简，最后构造了批处理OCRS，边和顶点到达模型的可选比率分别为0.337和0.5。这两个结果都改善了相应设置的现有技术。对于顶点到达，我们的结果是紧的。有趣的是，具有可比竞争比率的基于定价的预言者不平等是未知的。
We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is drawn independently from an a-priori known probability distribution. Under edge arrival, the weight of each edge is revealed upon arrival, and the algorithm decides whether to include it in the matching or not. Under vertex arrival, the weights of all edges from the newly arriving vertex to all previously arrived vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. To study these settings, we introduce a novel unified framework of batched prophet inequalities that captures online settings where elements arrive in batches; in particular it captures matching under the two aforementioned arrival models. Our algorithms rely on the construction of suitable online contention resolution schemes (OCRS). We first extend the framework of OCRS to batched-OCRS, we then establish a reduction from batched prophet inequality to batched OCRS, and finally we construct batched OCRSs with selectable ratios of 0.337 and 0.5 for edge and vertex arrival models, respectively. Both results improve the state of the art for the corresponding settings. For vertex arrival, our result is tight. Interestingly, pricing-based prophet inequalities with comparable competitive ratios are unknown.