Weighted Matching in the Random-Order Streaming and Robust Communication Models

We study the maximum weight matching problem in the random-order semi-streaming model and in the robust communication model. Unlike many other sublinear models, in these two frameworks, there is a large gap between the guarantees of the best known algorithms for the unweighted and weighted versions of the problem. In the random-order semi-streaming setting, the edges of an n-vertex graph arrive in a stream in a random order. The goal is to compute an approximate maximum weight matching with a single pass over the stream using O (n polylog n) space. Our main result is a (2/3-) -approximation algorithm for maximum weight matching in random-order streams, using space O (n n R), where R is the ratio between the heaviest and the lightest edge in the graph. Our result nearly matches the best known unweighted (2/3+₀) -approximation (where ₀ 10^-14 is a small constant) achieved by Assadi and Behnezhad ICALP 2021, and significantly improves upon previous weighted results. Our techniques also extend to the related robust communication model, in which the edges of a graph are partitioned randomly between Alice and Bob. Alice sends a single message of size O (n polylog n) to Bob, who must compute an approximate maximum weight matching. We achieve a (5/6-) -approximation using O (n n R) words of communication, matching the results of Azarmehr and Behnezhad ICALP 2023 for unweighted graphs.