论文标题
最大匹配问题的灵敏度分析
Sensitivity Analysis of the Maximum Matching Problem
论文作者
论文摘要
我们考虑算法对边缘和顶点修改的最大匹配问题的敏感性。具有低灵敏度的算法是可取的，因为它们对于边缘故障或攻击是可靠的。在这项工作中，我们显示了一个随机$（1-ε）$ - 近似算法，最差的敏感性$ o_im（1）$，在$（1-ε）$ - 近似算法上，Varma和Yoshida和Yoshida（Arxiv 2020）获得了平均敏感性$ n^ungitivity us（1-ε）近似算法，并有所改善。显示一个确定性$ 1/2 $ - APPROXIMATION算法，具有敏感性$ \ exp（o（\ log^*n））$用于有限学位图。我们表明，任何确定性的常数因子近似算法都必须具有灵敏度$ω（\ log^* n）$。我们的结果表明，随机算法比确定性算法更强大，因为前者可以实现敏感性，而不是$ n $，而后者则不能实现敏感性。我们还显示了顶点灵敏度的类似结果，在那里我们删除了顶点而不是边缘。作为结果的应用，我们为在tertex-arrival模型中的$o_ε（n）$ $o_ε（n）$提供了在线最大匹配的算法。相比之下，Bernstein等人。 （J. ACM 2019）给出了一种在线算法，该算法始终输出最大匹配，但仅用于两部分图形，并带有$ O（n \ log n）$总替换。 最后，我们介绍了归一化加权灵敏度的概念，这是符合已删除边缘权重的灵敏度的自然概括。我们表明，如果图中的所有边缘的重量都具有多个边界的重量，则给定一个权衡参数$α> 2 $，存在一种算法，该算法输出了$ \ frac {1} {1} {4α} $ - 以$ O（M \log_αn）$ fime，具有正常的权衡sensitive sensitivity $ o（1）$ o（1）$ o（1）。请参阅纸张以获取完整摘要。
We consider the sensitivity of algorithms for the maximum matching problem against edge and vertex modifications. Algorithms with low sensitivity are desirable because they are robust to edge failure or attack. In this work, we show a randomized $(1-ε)$-approximation algorithm with worst-case sensitivity $O_ε(1)$, which substantially improves upon the $(1-ε)$-approximation algorithm of Varma and Yoshida (arXiv 2020) that obtains average sensitivity $n^{O(1/(1+ε^2))}$ sensitivity algorithm, and show a deterministic $1/2$-approximation algorithm with sensitivity $\exp(O(\log^*n))$ for bounded-degree graphs. We show that any deterministic constant-factor approximation algorithm must have sensitivity $Ω(\log^* n)$. Our results imply that randomized algorithms are strictly more powerful than deterministic ones in that the former can achieve sensitivity independent of $n$ whereas the latter cannot. We also show analogous results for vertex sensitivity, where we remove a vertex instead of an edge. As an application of our results, we give an algorithm for the online maximum matching with $O_ε(n)$ total replacements in the vertex-arrival model. By comparison, Bernstein et al. (J. ACM 2019) gave an online algorithm that always outputs the maximum matching, but only for bipartite graphs and with $O(n\log n)$ total replacements. Finally, we introduce the notion of normalized weighted sensitivity, a natural generalization of sensitivity that accounts for the weights of deleted edges. We show that if all edges in a graph have polynomially bounded weight, then given a trade-off parameter $α>2$, there exists an algorithm that outputs a $\frac{1}{4α}$-approximation to the maximum weighted matching in $O(m\log_α n)$ time, with normalized weighted sensitivity $O(1)$. See paper for full abstract.
