论文标题
在线原始双重偶会在线匹配随机奖励：Configuration LP进行营救
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue
论文作者
论文摘要
Mehta和Panigrahi（Focs 2012）介绍了与随机奖励的在线匹配问题，其中边缘与成功概率相关联，并且与相应边缘的概率相关联。这是迄今为止Devanur，Jain和Kleinberg（Soda 2013）的少数在线匹配问题之一。本文通过采用配置线性程序，而不是以前的作品中使用的标准匹配线性程序来解锁在线匹配与随机奖励的随机匹配中的力量。 Our main result is a 0.572 competitive algorithm for the case of vanishing and unequal probabilities, improving the best previous bound of 0.534 by Mehta, Waggoner, and Zadimoghaddam (SODA 2015) and, in fact, is even better than the best previous bound of 0.567 by Mehta and Panigrahi (FOCS 2012) for the more restricted case of vanishing and equal probabilities.对于消失和均等的概率，我们获得了更好的竞争比率为0.576。由于随机在线原始双重分析的内在鲁棒性，我们的结果进一步推广到了顶点加权案例。
Mehta and Panigrahi (FOCS 2012) introduce the problem of online matching with stochastic rewards, where edges are associated with success probabilities and a match succeeds with the probability of the corresponding edge. It is one of the few online matching problems that have defied the randomized online primal dual framework by Devanur, Jain, and Kleinberg (SODA 2013) thus far. This paper unlocks the power of randomized online primal dual in online matching with stochastic rewards by employing the configuration linear program rather than the standard matching linear program used in previous works. Our main result is a 0.572 competitive algorithm for the case of vanishing and unequal probabilities, improving the best previous bound of 0.534 by Mehta, Waggoner, and Zadimoghaddam (SODA 2015) and, in fact, is even better than the best previous bound of 0.567 by Mehta and Panigrahi (FOCS 2012) for the more restricted case of vanishing and equal probabilities. For vanishing and equal probabilities, we get a better competitive ratio of 0.576. Our results further generalize to the vertex-weighted case due to the intrinsic robustness of the randomized online primal dual analysis.
