Laminar Families and Metric Embeddings: Non-bipartite Maximum Matching\n Problem in the Semi-Streaming Model

In this paper, we study the non-bipartite maximum matching problem in the\nsemi-streaming model. The maximum matching problem in the semi-streaming model\nhas received a significant amount of attention lately. While the problem has\nbeen somewhat well solved for bipartite graphs, the known algorithms for\nnon-bipartite graphs use $2^{\\frac1\\epsilon}$ passes or $n^{\\frac1\\epsilon}$\ntime to compute a $(1-\\epsilon)$ approximation. In this paper we provide the\nfirst FPTAS (polynomial in $n,\\frac1\\epsilon$) for the problem which is\nefficient in both the running time and the number of passes. We also show that\nwe can estimate the size of the matching in $O(\\frac1\\epsilon)$ passes using\nslightly superlinear space.\n To achieve both results, we use the structural properties of the matching\npolytope such as the laminarity of the tight sets and total dual integrality.\nThe algorithms are iterative, and are based on the fractional packing and\ncovering framework. However the formulations herein require exponentially many\nvariables or constraints. We use laminarity, metric embeddings and graph\nsparsification to reduce the space required by the algorithms in between and\nacross the iterations. This is the first use of these ideas in the\nsemi-streaming model to solve a combinatorial optimization problem.\n