Stochastic matching with few queries: (1-ε) approximation
Authors:
Open Access
- 22 June 2020
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1111-1124
Abstract
Suppose that we are given an arbitrary graph G=(V, E) and know that each edge in E is going to be realized independently with some probability p. The goal in the stochastic matching problem is to pick a sparse subgraph Q of G such that the realized edges in Q, in expectation, include a matching that is approximately as large as the maximum matching among the realized edges of G. The maximum degree of Q can depend on p, but not on the size of G. This problem has been subject to extensive studies over the years and the approximation factor has been improved gradually from 0.5 to eventually 2/3 which is a known barrier. In this work, we analyze a natural sampling-based algorithm and show that it can obtain a (1−є) approximation, for any constant є > 0. A key and of possible independent interest component of our analysis is an algorithm that constructs a matching on a stochastic graph, which among some other important properties, guarantees that each vertex is matched independently from the vertices that are sufficiently far. This allows us to bypass a previously known barrier towards achieving (1−є) approximation based on existence of dense Ruzsa-Szemerédi graphs.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Stochastic matching with few queries: (1-ε) approximation2020
- Distributed Maximal Independent Set using Small Messages2019
- The Stochastic Matching Problem2017
- Ignorance is Almost Bliss2015
- Better bounds for matchings in the streaming model2013
- Nearly complete graphs decomposable into large induced matchings and their applications2012
- On the communication and streaming complexity of maximum bipartite matching2012
- Monotonicity testing over general poset domains2002
- Locality in Distributed Graph AlgorithmsSIAM Journal on Computing, 1992
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965