Bipartite Matching in the Semi-streaming Model
Bipartite Matching in the Semi-streaming Model
复制标题
半流模型中的二分匹配
DOI：
10.1007/s00453-011-9556-8
复制
发表时间：
2011
期刊：
影响因子：
1.1
通讯作者：
A. Srivastav
中科院分区：
文献类型：
--
作者：
S. Eggert;Lasse Kliemann;Peter Munstermann;A. Srivastav
我们提出了第一个确定性的1+ε近似算法，用于在半流模型中在两分的图中找到大型匹配，该模型仅需要O（（1/ε）5）通过此模型中的输入图。 g =（v，e）以某种任意顺序给出了其边缘的流，算法的存储由o（npolylog n）位界定，其中\ documentClass [12pt] {minimal} \ usepackage {amsmath} \ amsmath} \ usepackage {wasysym} \ usepackage {amsfonts} \ usepackage {amssymb} \ usepackage {amsbsy} \ usepackage {mathrsfs} { v} \ rvert $ \ end {document}。 ，美国，第170-181页，2005年），使用ω（（1/ε）1/ε）通过。通过，在近似参数中是必要的指数。复杂性降低并消除随机化。我们使用增强路径的长度为2k+1的长度，当时我们终止了一个迭代的数量。一定的阈值也取决于K，确保1+ε近似是在不需要多次迭代的情况下找到那些增强路径的情况。 ，将每个边缘视为可能在流中出现的可能的扩展。然后，通过回溯将其删除，仅在严格的位置下再次将其插入一条路径。
We present the first deterministic 1+ε approximation algorithm for finding a large matching in a bipartite graph in the semi-streaming model which requires only O((1/ε)5) passes over the input stream. In this model, the input graph G=(V,E) is given as a stream of its edges in some arbitrary order, and storage of the algorithm is bounded by O(npolylog n) bits, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$n = \lvert {V}\rvert $\end{document}. The only previously known arbitrarily good approximation for general graphs is achieved by the randomized algorithm of McGregor (Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and Randomization and Computation, Berkeley, CA, USA, pp. 170–181, 2005), which uses Ω((1/ε)1/ε) passes. We show that even for bipartite graphs, McGregor’s algorithm needs Ω(1/ε)Ω(1/ε) passes, thus it is necessarily exponential in the approximation parameter. The design as well as the analysis of our algorithm require the introduction of some new techniques. A novelty of our algorithm is a new deterministic assignment of matching edges to augmenting paths which is responsible for the complexity reduction, and gets rid of randomization. We repeatedly grow an initial matching using augmenting paths up to a length of 2k+1 for k=⌈2/ε⌉. We terminate when the number of augmenting paths found in one iteration falls below a certain threshold also depending on k, that guarantees a 1+ε approximation. The main challenge is to find those augmenting paths without requiring an excessive number of passes. In each iteration, using multiple passes, we grow a set of alternating paths in parallel, considering each edge as a possible extension as it comes along in the stream. Backtracking is used on paths that fail to grow any further. Crucial are the so-called position limits: when a matching edge is the ith matching edge in a path and it is then removed by backtracking, it will only be inserted into a path again at a position strictly lesser than i. This rule strikes a balance between terminating quickly on the one hand and giving the procedure enough freedom on the other hand.