Faster Fully Dynamic Matchings with Small Approximation Ratios
Faster Fully Dynamic Matchings with Small Approximation Ratios
复制标题
具有小近似比的更快的全动态匹配
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Cliff Stein
中科院分区：
文献类型：
--
作者：
A. Bernstein;Cliff Stein
最大的基数匹配是许多算法和应用程序的基本算法问题，其中插入边缘和删除的边缘也已成为许多动态匹配的主题。边缘图）分为两组：有快速（主要是随机的）算法，可以实现2个附近或更差，并且具有慢速算法ω（[等式]）更新时间比2近似更好。 -2近似值我们以前回答了这个问题，只有两分的特殊情况是我们的主要结果。在摊销更新时间O（M1/4E - 2.5）中，维持（3/2 + e） - Approximation，除了实现上述权衡外，我们的算法在多个月上都比所有现有的确定性算法都更快（不包括现有的对数n-Approximation Onak和Rubinfeld），同时仍保持更好的近似值。 e） - 在最差的时间o（α（α + log n））中，对于恒定e时，在最差的时间o（α（α + log n））中，Approximate分数匹配或Appro-Approximate积分匹配。 n）当树木为小层次时，更新时间也是小型弧形的结果。路径。我们定义了一个中间图，称为EDCS，并显示EDCS H包含大型匹配，并显示如何在G中维持EDC。一般图中的不同图表。在本文中，我们在H中明确构建了一个大的分数匹配。在某些情况下，我们可以保证该分数匹配是γ限制的，这意味着它仅在[0，然后，我们将这种匹配与非双分化图中最大匹配的新结构属性相结合，这类似于双分部分图中最大匹配所引起的切割。
Maximum cardinality matching is a fundamental algorithmic problem with many algorithms and applications. The fully dynamic version, in which edges are inserted and deleted over time has also been the subject of much attention. Existing algorithms for dynamic matching (in general n-vertex m-edge graphs) fall into two groups: there are fast (mostly randomized) algorithms that achieve a 2-approximation or worse, and there are slow algorithms with Ω([EQUATION]) update time that achieve a better-than-2 approximation. Thus the obvious question is whether we can design an algorithm that achieves a tradeoff between these two: a o([EQUATION]) update time and a better-than-2 approximation simultaneously. We answer this question in the affirmative. Previously, such bounds were only known for the special case of bipartite graphs. Our main result is a fully dynamic deterministic algorithm that maintains a (3/2 + e)-approximation in amortized update time O(m1/4e--2.5). In addition to achieving the trade-off described above, our algorithm manages to be polynomially faster than all existing deterministic algorithms (excluding an existing log n-approximation of Onak and Rubinfeld), while still maintaining a better-than-2 approximation. We also give stronger results for graphs whose arboricity is at most α. We show how to maintain a (1 + e)-approximate fractional matching or a (3/2 + e)-approximate integral matching in worst-case time O(α(α + log n)) for constant e. When the arboricity is constant, this bound is O(log n) and when the arboricity is polylogarithmic the update time is also polylogarithmic. Previous results for small arboricity non-bipartite graphs could only maintain a maximal matching (2-approximation). We maintain the approximate matching without explicitly using augmenting paths. We define an intermediate graph, called an EDCS and show that the EDCS H contains a large matching, and show how to maintain an EDCS in G. The EDCS was used in previous works on bipartite graphs, however the details and proofs are completely different in general graphs. The algorithm for bipartite graphs relies on ideas from flows and cuts to non-constructively prove the existence of a good matching in H, but these ideas do not seem to extend to non-bipartite graphs. In this paper we instead explicitly construct a large fractional matching in H. In some cases we can guarantee that this fractional matching is γ-restricted, which means that it only uses values either in the range [0, γ] or 1. We then combine this matching with a new structural property of maximum matchings in non-bipartite graphs, which is analogous to the cut induced by maximum matchings in bipartite graphs.