Stochastic Weighted Matching: (1-ϵ) Approximation
Soheil Behnezhad, Mahsa Derakhshan · 2020
Let G = (V, E) be a given edge-weighted graph and let its realization G be a random subgraph of G that includes each edge e ∈ E independently with probability p. We study a stochastic matching problem where the goal is to non-adaptively pick a sparse subgraph Q of G (without knowing the realization G), such that the maximum weight matching among the realized edges of Q (i.e. graph Q∩G) in expectation approximates the maximum weight matching of the whole realization G. In this paper, we prove that for any ε ∈ (0,1), every graph G has a subgraph Q that has maximum degree only Oε, p(1) and guarantees a ( 1-ε) -approximation. That is, the maximum degree of Q depends only on ε and p (both of which are known to be necessary) and not for example on the number of nodes in G, the edge-weights, etc. The stochastic matching problem has been studied extensively on both weighted and unweighted graphs. Previously, only existence of (close to) half-approximate subgraphs was known for weighted graphs [Yamaguchi and Maehara, SODA'18; Behnezhad et al., SODA'19]. Our result substantially improves over these works, matches the state-of-the-art for unweighted graphs [Behnezhad et al., STOC'20], and settles the approximation factor.