2020/04/18 by Soheil Behnezhad, Behnezhad, Soheil, Mahsa Derakhshan +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2004.08703
openalex publication_date 2020/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G=(V, E) be a given edge-weighted graph and let its em realization\n\G be a random subgraph of G that includes each edge e \∈ E\nindependently with probability p. In the em stochastic matching problem,\nthe goal is to pick a sparse subgraph Q of G without knowing the\nrealization \G, such that the maximum weight matching among the\nrealized edges of Q (i.e. graph Q \∩ \G) in expectation\napproximates the maximum weight matching of the whole realization\n\G.\n In this paper, we prove that for any desirably small \ε \∈ (0, 1),\nevery graph G has a subgraph Q that guarantees a\n(1-\ε)-approximation and has maximum degree only O\ε, p(1).\nThat is, the maximum degree of Q depends only on \ε and p (both of\nwhich are known to be necessary) and not for example on the number of nodes in\nG, the edge-weights, etc.\n The stochastic matching problem has been studied extensively on both weighted\nand unweighted graphs. Previously, only existence of (close to)\nhalf-approximate subgraphs was known for weighted graphs [Yamaguchi and\nMaehara, SODA'18; Behnezhad et al., SODA'19]. Our result substantially improves\nover these works, matches the state-of-the-art for unweighted graphs [Behnezhad\net al., STOC'20], and essentially settles the approximation factor.\n