English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The problem of finding a maximum size matching in a graph (known as themaximum matching problem) is one of the most classical problems in computerscience. Despite a significant body of work dedicated to the study of thisproblem in the data stream model, the state-of-the-art single-passsemi-streaming algorithm for it is still a simple greedy algorithm thatcomputes a maximal matching, and this way obtains 1/2-approximation. Someprevious works described two/three-pass algorithms that improve over thisapproximation ratio by using their second and third passes to improve the abovementioned maximal matching. One contribution of this paper continuous this lineof work by presenting new three-pass semi-streaming algorithms that work alongthese lines and obtain improved approximation ratios of 0.6111 and 0.5694 fortriangle-free and general graphs, respectively.  Unfortunately, a recent work (Konrad and Naidu, 2021) shows that the strategyof constructing a maximal matching in the first pass and then improving it infurther passes has limitations. Additionally, this technique is unlikely to getus closer to single-pass semi-streaming algorithms obtaining a better than1/2-approximation. Therefore, it is interesting to come up with algorithms thatdo something else with their first pass (we term such algorithmsnon-maximal-matching-first algorithms). No such algorithms are currently known(to the best of our knowledge), and the main contribution of this paper isdescribing such algorithms that obtain approximation ratios of 0.5384 and0.5555 in two and three passes, respectively, for general graphs (the resultfor three passes improves over the previous state-of-the-art, but is worse thanthe result of this paper mentioned in the previous paragraph for generalgraphs).

Maximum Matching sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model