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 log n log 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 + ϵ0)-approximation (where ϵ0 ∼ 10−14 is a small constant) achieved by Assadi and Behnezhad [6], 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 log n log R) words of communication, matching the results of Azarmehr and Behnezhad [20] for unweighted graphs.