ﻻ يوجد ملخص باللغة العربية
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^{frac1epsilon}$ passes or $n^{frac1epsilon}$ time to compute a $(1-epsilon)$ approximation. In this paper we provide the first FPTAS (polynomial in $n,frac1epsilon$) 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(frac1epsilon)$ 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.
In this paper, we study linear programming based approaches to the maximum matching problem in the semi-streaming model. The semi-streaming model has gained attention as a model for processing massive graphs as the importance of such graphs has incre
We prove a lower bound on the space complexity of two-pass semi-streaming algorithms that approximate the maximum matching problem. The lower bound is parameterized by the density of Ruzsa-Szemeredi graphs: * Any two-pass semi-streaming algorithm f
We present a deterministic $(1+varepsilon)$-approximate maximum matching algorithm in $mathsf{poly}(1/varepsilon)$ passes in the semi-streaming model, solving the long-standing open problem of breaking the exponential barrier in the dependence on $1/
The optimized assignment of staff is of great significance for improving the production efficiency of the society. For specific tasks, the key to optimizing staffing is personnel scheduling. The assignment problem is classical in the personnel schedu
We study the problem of parameterized matching in a stream where we want to output matches between a pattern of length m and the last m symbols of the stream before the next symbol arrives. Parameterized matching is a natural generalisation of exact