  The problem of finding a maximum size matching in a graph (known as the
maximum matching problem) is one of the most classical problems in computer
science. Despite a significant body of work dedicated to the study of this
problem in the data stream model, the state-of-the-art single-pass
semi-streaming algorithm for it is still a simple greedy algorithm that
computes a maximal matching, and this way obtains 1/2-approximation. Some
previous works described two/three-pass algorithms that improve over this
approximation ratio by using their second and third passes to improve the above
mentioned maximal matching. One contribution of this paper continuous this line
of work by presenting new three-pass semi-streaming algorithms that work along
these lines and obtain improved approximation ratios of 0.6111 and 0.5694 for
triangle-free and general graphs, respectively.
  Unfortunately, a recent work (Konrad and Naidu, 2021) shows that the strategy
of constructing a maximal matching in the first pass and then improving it in
further passes has limitations. Additionally, this technique is unlikely to get
us closer to single-pass semi-streaming algorithms obtaining a better than
1/2-approximation. Therefore, it is interesting to come up with algorithms that
do something else with their first pass (we term such algorithms
non-maximal-matching-first algorithms). No such algorithms are currently known
(to the best of our knowledge), and the main contribution of this paper is
describing such algorithms that obtain approximation ratios of 0.5384 and
0.5555 in two and three passes, respectively, for general graphs (the result
for three passes improves over the previous state-of-the-art, but is worse than
the result of this paper mentioned in the previous paragraph for general
graphs).
