Laminar Families and Metric Embeddings: Non-bipartite Maximum Matching Problem in the Semi-Streaming Model
Laminar Families and Metric Embeddings: Non-bipartite Maximum Matching Problem in the Semi-Streaming Model
复制标题
DOI：
--
复制
发表时间：
2011-04
期刊：
影响因子：
--
通讯作者：
Kook Jin Ahn;S. Guha
中科院分区：
文献类型：
--
作者：
Kook Jin Ahn;S. Guha
本文研究了半流模型中的非二部最大匹配问题。最近，半流模型中的最大匹配问题受到了广泛的关注。虽然这个问题对于二部图已经得到了很好的解决，但已知的非二部图的算法使用$2^{\Frac1\epsilon}$遍或$n^{\Frac1\epsilon}$时间来计算$(1-\epsilon)$近似。本文给出了该问题的第一个FPTAS($n中的多项式)，它在运行时间和通过次数上都是有效的。我们还证明了我们可以使用略微超线性空间来估计$O(Frac1\epsilon)$Pass中匹配的大小。为了达到这两个结果，我们利用匹配多面体的结构性质，如紧集的层次性和全对偶完整性。该算法是迭代的，并且基于分数填充和覆盖框架。然而，这里的公式需要成倍增加的变量或约束。我们使用层次化、度量嵌入和图稀疏来减少算法在迭代之间和迭代之间所需的空间。这是首次在半流模型中使用这些思想来解决组合优化问题。
In this paper, we study the non-bipartite maximum matching problem in the semi-streaming model. The maximum matching problem in the semi-streaming model has received a significant amount of attention lately. While the problem has been somewhat well solved for bipartite graphs, the known algorithms for non-bipartite graphs use $2^{\frac1\epsilon}$ passes or $n^{\frac1\epsilon}$ time to compute a $(1-\epsilon)$ approximation. In this paper we provide the first FPTAS (polynomial in $n,\frac1\epsilon$) for the problem which is efficient in both the running time and the number of passes. We also show that we can estimate the size of the matching in $O(\frac1\epsilon)$ passes using slightly superlinear space. To achieve both results, we use the structural properties of the matching polytope such as the laminarity of the tight sets and total dual integrality. The algorithms are iterative, and are based on the fractional packing and covering framework. However the formulations herein require exponentially many variables or constraints. We use laminarity, metric embeddings and graph sparsification to reduce the space required by the algorithms in between and across the iterations. This is the first use of these ideas in the semi-streaming model to solve a combinatorial optimization problem.