  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.
