Stochastic Weighted Matching: (1-ε) Approximation
share
Let G=(V, E) be a given edge-weighted graph and let its realizationG be a random subgraph of G that includes each edge e ∈ E independently with probability p. In the stochastic matching problem, the goal is to 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 desirably small ϵ∈ (0, 1), every graph G has a subgraph Q that guarantees a (1-ϵ)-approximation and has maximum degree only O_ϵ, p(1). 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 essentially settles the approximation factor.
READ FULL TEXT