AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, SWS, RG1, MMCI   Info

AG Audience

English

30 Minutes

We study the maximum weight matching problem in the random-order semi-streaming model. 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. Bernstein gave a 2/3-approximation algorithm for maximum cardinality matching problem by adapting the “matching sparsifier” Edge-Degree Constrained Subgraph (EDCS) to the streaming context. Subsequent work by Assadi and Behnezhad improved upon this, achieving a (2/3 +ε0)-approximation by simultaneously running Bernstein’s algorithm while identifying short augmenting paths. For adversarial streams, Bernstein, Dudeja, and Langley introduced a reduction from maximum weight matching to maximum cardinality matching. However, progress in random-order streams has been limited. In this work we reduce the maximum weighted matching in random order stream problem to the maximum cardinality matching in random batch and designed a (2/3 -ε)- approximation algorithm for this problem.

Ina Geisler

+49 681 9325 1802

--email hidden

Zoom

passcode not visible

logged in users only