论文标题
最大重量在线随机匹配：改进了针对在线基准的近似值
Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark
论文作者
论文摘要
在本文中，我们研究了顶点和边缘到达的在线双分图上的最大重量随机匹配。我们专注于设计相对于在线基准测试的多项式时间近似算法，Papadimitriou，Pollner，Saberi和Wajc [EC'21]首先考虑了该算法。 在该问题的顶点到达版本中，目标是在图表中的一个部分以固定顺序在线到达，并独立失败的机会，找到给定的两部分图的最大最大重量匹配。每当一个顶点到达时，我们都应该不可撤销地决定是否将其与它的一个无与伦比的邻居匹配或永远保持无与伦比。相对于离线基准（先知），针对此问题的不同变体的近似算法进行了长长的工作设计。但是，Papadimitriou等人提出了替代性的在线基准，并表明，考虑到这种新的基准，他们可以提高0.5近似值，这是相对于离线基准测试的最佳比率。它们提供了0.51个approximation算法，后来Saberi和Wajc [ICALP'21]将其提高到0.526。本文的主要贡献是设计一种简单的算法，对于此问题，其近似值显着提高了（1-1/e）。 我们还考虑了边缘到达版本，其中图形的边缘以在线方式到达具有独立失败机会的在线方式。还对此问题的设计近似算法也进行了广泛的研究，相对于离线基准，最佳近似比为0.337。但是，本文是第一个考虑问题的边缘到达版本的在线基准。对于此问题，我们提供了一种简单的算法，相对于在线基准，近似值为0.5。
In this paper, we study max-weight stochastic matchings on online bipartite graphs under both vertex and edge arrivals. We focus on designing polynomial time approximation algorithms with respect to the online benchmark, which was first considered by Papadimitriou, Pollner, Saberi, and Wajc [EC'21]. In the vertex arrival version of the problem, the goal is to find an approximate max-weight matching of a given bipartite graph when the vertices in one part of the graph arrive online in a fixed order with independent chances of failure. Whenever a vertex arrives we should decide, irrevocably, whether to match it with one of its unmatched neighbors or leave it unmatched forever. There has been a long line of work designing approximation algorithms for different variants of this problem with respect to the offline benchmark (prophet). Papadimitriou et al., however, propose the alternative online benchmark and show that considering this new benchmark allows them to improve the 0.5 approximation ratio, which is the best ratio achievable with respect to the offline benchmark. They provide a 0.51-approximation algorithm which was later improved to 0.526 by Saberi and Wajc [ICALP'21]. The main contribution of this paper is designing a simple algorithm with a significantly improved approximation ratio of (1-1/e) for this problem. We also consider the edge arrival version in which, instead of vertices, edges of the graph arrive in an online fashion with independent chances of failure. Designing approximation algorithms for this problem has also been studied extensively with the best approximation ratio being 0.337 with respect to the offline benchmark. This paper, however, is the first to consider the online benchmark for the edge arrival version of the problem. For this problem, we provide a simple algorithm with an approximation ratio of 0.5 with respect to the online benchmark.
