ﻻ يوجد ملخص باللغة العربية
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 from $0.5$ to $0.5001$ to $0.6568$ and eventually to $2/3$. In this work, we analyze a natural sampling-based algorithm and show that it can obtain all the way up to $(1-epsilon)$ approximation, for any constant $epsilon > 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-epsilon)$ approximation based on existence of dense Ruzsa-Szemeredi graphs.
We consider the following stochastic matching problem on both weighted and unweighted graphs: A graph $G(V, E)$ along with a parameter $p in (0, 1)$ is given in the input. Each edge of $G$ is realized independently with probability $p$. The goal is t
Let $G=(V, E)$ be a given edge-weighted graph and let its {em realization} $mathcal{G}$ be a random subgraph of $G$ that includes each edge $e in E$ independently with probability $p$. In the {em stochastic matching} problem, the goal is to pick a sp
Leveraging tools of De, Mossel, and Neeman [FOCS, 2019], we show two different results pertaining to the emph{tolerant testing} of juntas. Given black-box access to a Boolean function $f:{pm1}^{n} to {pm1}$, we give a $poly(k, frac{1}{varepsilon})$ q
We present a deterministic $(1+varepsilon)$-approximate maximum matching algorithm in $mathsf{poly}(1/varepsilon)$ passes in the semi-streaming model, solving the long-standing open problem of breaking the exponential barrier in the dependence on $1/
Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of randomized NC matching algorithms [KUW85, MVV87]. Over the last fi