Stochastic Weighted Matching: (1-ϵ) Approximation
Authors:
- 1 November 2020
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1392-1403
Abstract
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.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Stochastic matching with few queries: (1-ε) approximation2020
- Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few QueriesOperations Research, 2020
- Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs2019
- Stochastic Matching on Uniformly Sparse Graphs2019
- Stochastic Matching with Few Queries: New Algorithms and Tools2019
- Almost Optimal Stochastic Weighted Matching with Few Queries2018
- Stochastic Packing Integer Programs with Few Queries2018
- The Stochastic Matching Problem2017
- The Stochastic Matching Problem with (Very) Few Queries2016
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965