2023/11/14 by Derakhshan, Mahsa, Saneian, Mohammad · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2311.08513
In this paper, we study the weighted stochastic matching problem. 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 a known probability pe. The goal in this problem is to pick a sparse subgraph Q of G without prior knowledge of G's realization, such that the maximum weight matching among the realized edges of Q (i.e. the subgraph Q∩ G) in expectation approximates the maximum weight matching of the entire realization G. Attaining any constant approximation ratio for this problem requires selecting a subgraph of max-degree Ω(1/p) where p=mine∈ E pe. On the positive side, there exists a (1-ε)-approximation algorithm by Behnezhad and Derakhshan, albeit at the cost of max-degree having exponential dependence on 1/p. Within the poly(1/p) regime, however, the best-known algorithm achieves a 0.536 approximation ratio due to Dughmi, Kalayci, and Patel improving over the 0.501 approximation algorithm by Behnezhad, Farhadi, Hajiaghayi, and Reyhani. In this work, we present a 0.68 approximation algorithm with O(1/p) queries per vertex, which is asymptotically tight. This is even an improvement over the best-known approximation ratio of 2/3 for unweighted graphs within the poly(1/p) regime due to Assadi and Bernstein. The 2/3 approximation ratio is proven tight in the presence of a few correlated edges in G, indicating that surpassing the 2/3 barrier should rely on the independent realization of edges. Our analysis involves reducing the problem to designing a randomized matching algorithm on a given stochastic graph with some variance-bounding properties.