Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStochastic Matching with Few Queries: $(1-varepsilon)$ Approximation
183
0
0.0
(
0
)
Added by
Soheil Behnezhad
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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 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.
rate research
Read More
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 to select a degree bounded (dependent only on $p$) subgraph $H$ of $G$ such that the expected size/weight of maximum realized matching of $H$ is close to that of $G$. This model of stochastic matching has attracted significant attention over the recent years due to its various applications. The most fundamental open question is the best approximation factor achievable for such algorithms that, in the literature, are referred to as non-adaptive algorithms. Prior work has identified breaking (near) half-approximation as a barrier for both weighted and unweighted graphs. Our main results are as follows: -- We analyze a simple and clean algorithm and show that for unweighted graphs, it finds an (almost) $4sqrt{2}-5$ ($approx 0.6568$) approximation by querying $O(frac{log (1/p)}{p})$ edges per vertex. This improves over the state-of-the-art $0.5001$ approximate algorithm of Assadi et al. [EC17]. -- We show that the same algorithm achieves a $0.501$ approximation for weighted graphs by querying $O(frac{log (1/p)}{p})$ edges per vertex. This is the first algorithm to break $0.5$ approximation barrier for weighted graphs. It also improves the per-vertex queries of the state-of-the-art by Yamaguchi and Maehara [SODA18] and Behnezhad and Reyhani [EC18]. Our algorithms are fundamentally different from prior works, yet are very simple and natural. For the analysis, we introduce a number of procedures that construct heavy fractional matchings. We consider the new algorithms and our analytical tools to be the main contributions of this paper.
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 sparse subgraph $Q$ of $G$ without knowing the realization $mathcal{G}$, such that the maximum weight matching among the realized edges of $Q$ (i.e. graph $Q cap mathcal{G}$) in expectation approximates the maximum weight matching of the whole realization $mathcal{G}$. In this paper, we prove that for any desirably small $epsilon in (0, 1)$, every graph $G$ has a subgraph $Q$ that guarantees a $(1-epsilon)$-approximation and has maximum degree only $O_{epsilon, p}(1)$. That is, the maximum degree of $Q$ depends only on $epsilon$ 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, SODA18; Behnezhad et al., SODA19]. Our result substantially improves over these works, matches the state-of-the-art for unweighted graphs [Behnezhad et al., STOC20], and essentially settles the approximation factor.
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})$ query algorithm that distinguishes between functions that are $gamma$-close to $k$-juntas and $(gamma+varepsilon)$-far from $k$-juntas, where $k = O(frac{k}{varepsilon^2})$. In the non-relaxed setting, we extend our ideas to give a $2^{tilde{O}(sqrt{k/varepsilon})}$ (adaptive) query algorithm that distinguishes between functions that are $gamma$-close to $k$-juntas and $(gamma+varepsilon)$-far from $k$-juntas. To the best of our knowledge, this is the first subexponential-in-$k$ query algorithm for approximating the distance of $f$ to being a $k$-junta (previous results of Blais, Canonne, Eden, Levi, and Ron [SODA, 2018] and De, Mossel, and Neeman [FOCS, 2019] required exponentially many queries in $k$). Our techniques are Fourier analytical and make use of the notion of normalized influences that was introduced by Talagrand [AoP, 1994].
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/varepsilon$. Our algorithm exponentially improves on the well-known randomized $(1/varepsilon)^{O(1/varepsilon)}$-pass algorithm from the seminal work by McGregor [APPROX05], the recent deterministic algorithm by Tirodkar with the same pass complexity [FSTTCS18], as well as the deterministic $log n cdot mathsf{poly}(1/varepsilon)$-pass algorithm by Ahn and Guha [ICALP11].
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 five years, the theoretical computer science community has launched a relentless attack on this question, leading to the discovery of several powerful ideas. We give what appears to be the culmination of this line of work: An NC algorithm for finding a minimum-weight perfect matching in a general graph with polynomially bounded edge weights, provided it is given an oracle for the decision problem. Consequently, for settling the main open problem, it suffices to obtain an NC algorithm for the decision problem. We believe this new fact has qualitatively changed the nature of this open problem. All known efficient matching algorithms for general graphs follow one of two approaches: given by Edmonds [Edm65] and Lovasz [Lov79]. Our oracle-based algorithm follows a new approach and uses many of the ideas discovered in the last five years. The difficulty of obtaining an NC perfect matching algorithm led researchers to study matching vis-a-vis clever relaxations of the class NC. In this vein, recently Goldwasser and Grossman [GG15] gave a pseudo-deterministic RNC algorithm for finding a perfect matching in a bipartite graph, i.e., an RNC algorithm with the additional requirement that on the same graph, it should return the same (i.e., unique) perfect matching for almost all choices of random bits. A corollary of our reduction is an analogous algorithm for general graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
