论文标题
在随机发展的图中匹配
Matching in Stochastically Evolving Graphs
论文作者
论文摘要
本文研究了随机发展的图表中最大的基数匹配问题。我们通过随机出发正式定义到达 - 开发模型。在那里，从特定的概率分布中取样图，并显示为一系列快照。我们的目标是研究在采样图中创建较大匹配的算法。我们为这个问题定义了随机性的价格，该问题从直观地捕获了由于模型的不确定性而在最坏情况下，在最坏的情况下，在最坏情况下丢失了任何算法。此外，我们证明了该问题的确定性最佳算法的存在。在第二组结果中，我们表明我们可以通过得出完全随机的近似方案（FPRA）来有效地近似最大基数匹配的预期大小。 FPRA是概率算法的骨干，当模型在两个时间段上定义时，它是最佳的。我们的最后结果是$ \ frac {2} {3} $的上限，其价格是随机性的。这意味着没有算法可以匹配超过$ \ frac {2} {3} $的$ \ frac {3} $，这是事后最佳匹配的边缘。
This paper studies the maximum cardinality matching problem in stochastically evolving graphs. We formally define the arrival-departure model with stochastic departures. There, a graph is sampled from a specific probability distribution and it is revealed as a series of snapshots. Our goal is to study algorithms that create a large matching in the sampled graphs. We define the price of stochasticity for this problem which intuitively captures the loss of any algorithm in the worst case in the size of the matching due to the uncertainty of the model. Furthermore, we prove the existence of a deterministic optimal algorithm for the problem. In our second set of results we show that we can efficiently approximate the expected size of a maximum cardinality matching by deriving a fully randomized approximation scheme (FPRAS) for it. The FPRAS is the backbone of a probabilistic algorithm that is optimal when the model is defined over two timesteps. Our last result is an upper bound of $\frac{2}{3}$ on the price of stochasticity. This means that there is no algorithm that can match more than $\frac{2}{3}$ of the edges of an optimal matching in hindsight.
