Maximum Weight b-Matchings in Random-Order Streams
share
We consider the maximum weight b-matching problem in the random-order semi-streaming model. Assuming all weights are small integers drawn from [1,W], we present a 2 - 1/2W + ε approximation algorithm, using a memory of O(max(|M_G|, n) · poly(log(m),W,1/ε)), where |M_G| denotes the cardinality of the optimal matching. Our result generalizes that of Bernstein [Bernstein, 2015], which achieves a 3/2 + ε approximation for the maximum cardinality simple matching. When W is small, our result also improves upon that of Gamlath et al. [Gamlath et al., 2019], which obtains a 2 - δ approximation (for some small constant δ∼ 10^-17) for the maximum weight simple matching. In particular, for the weighted b-matching problem, ours is the first result beating the approximation ratio of 2. Our technique hinges on a generalized weighted version of edge-degree constrained subgraphs, originally developed by Bernstein and Stein [Bernstein and Stein, 2015]. Such a subgraph has bounded vertex degree (hence uses only a small number of edges), and can be easily computed. The fact that it contains a 2 - 1/2W + ε approximation of the maximum weight matching is proved using the classical Kőnig-Egerváry's duality theorem.
READ FULL TEXT