Query Efficient Weighted Stochastic Matching

Since its introduction in the pioneering work of Blum, Dickerson, Haghtalab, Procaccia, Sandholm, and Sharma [11], the stochastic matching problem has received considerable attention [11, 2, 3, 18, 10, 9, 1, 7, 8, 6]. It is established by Assadi, Khanna, and Li [2] that attaining any constant approximation ratio for this problem requires selecting a subgraph of maximum degree $\mathrm{\Omega }(1/p)$, where $p={\min }_{e\in E}{p}_e$.

Yamaguchi and Maehara [18] were the first to consider the weighted version of the problem. They provided a $0.5-\epsilon$ approximation algorithm via $O(W\log n/p)$ queries per vertex, where $W$ is the largest edge weight. Their query complexity was later improved to $\mathrm{poly}(1/p)$ by Behnezhad and Reyhani [10]. Subsequently, Behnezhad, Farhadi, Hajiaghayi, and Reyhani [9] provided the first algorithm breaking the $0.5$ approximation via $O(1/p)$ queries per vertex. Finally, Dughmi, Kalayci, and Patel [12] improved this approximation ratio to $0.536$ using an asymptotically optimal number of queries. In a separate line of work, Behnezhad and Derakhshan [6] showed that if $\exp (1/p)$ queries per vertex are allowed, it is possible to improve this approximation ratio up to $1-\epsilon$.

For the unweighted version of the problem, the pioneering work of Blum et al. [11] provides a $0.5$ approximation via $\mathrm{poly}(1/p)$ queries per vertex. After a series of works [9, 3], this approximation ratio was improved to $2/3$ via $O(\log (1/p)/p)$ queries by Assadi and Bernstein [1]. For the special case of unweighted bipartite graphs, Behnezhad, Blum, and Derakhshan improved this approximation ratio to $0.73$ [5]. Behnezhad, Derakhshan, and Hajiaghayi [8] were the first to obtain a $(1-\epsilon )$-approximation, albeit using $\exp (1/p)$ queries per vertex. Finally, in a recent breakthrough result, Azarmehr, Behnezhad, Ghafari, and Rubinfeld [4] improved this query complexity to ${(1/p)}^{\exp (1/\epsilon )}$.

The framework utilized to analyze the aforementioned algorithm involves partitioning the edges into two categories: crucial and non-crucial. Separate arguments are then presented to demonstrate how these edges can be integrated to construct a large weight enough matching in $𝒬$. Let $x_e$ denote the probability of edge $e$ being part of the optimal solution, i.e.,

We define the set of crucial edges, denoted by $C$, and the set of non-crucial edges, denoted by $N$, as follows:

where $\tau$ is a fixed threshold in the order of $p$. Note that by choosing a sufficiently large value for $t=O1/p$, we can ensure that $Q$ contains nearly all of the crucial edges. To establish the existence of a large weight matching in $𝒢$, the first step is to construct a matching $M_c$ exclusively on the crucial edges which is an $\alpha$-approximation with respect to the contribution of the crucial edges to the optimal solution. ($M_c$ should satisfy some other useful properties which we will discuss later.) The next step is constructing a fractional matching $𝒇$ on the subgraph of non-crucial edges whose endpoints are unmatched in $M_c$. This fractional matching should satisfy the two following properties: first, for any edge $e\in N$, it holds that $\text{E}[f_e]\simeq x_e$; second, the values of $f_e$ should be small enough to ensure that $𝒇$ has almost no integrality gap. By combining these steps, the framework constructs a matching with weight almost $\alpha \times 𝖶(\text{MWM}(𝒢)\cap C)+𝖶(\text{MWM}(𝒢)\cap N)$. Here $𝖶(.)$ is a function returning the weight of a given matching.

All papers utilizing this analysis framework require the algorithm used for constructing $M_c$ to match the endpoints of any non-crucial edge $e$ independently. Otherwise, the edge is discarded. This requirement is the main reason why Behnezhad and Derakhshan [6] need to take an exponential number of edges per vertex. To achieve this property, they employ a distributed LOCAL algorithm for constructing $M_c$, which can lead to a vertex being dependent on the vertices within its $\mathrm{\Omega }(\log (\mathrm{\Delta }))$ radius ball, where $\mathrm{\Delta }$ denotes the crucial degree of a vertex. Since potentially ${(1/p)}^{\log (1/p)}$ non-crucial edges may be discarded for each vertex, these edges need to have small $x_e$ values. Consequently, a small threshold $\tau$ and a large $t$ must be chosen. Due to known lower bounds for matching in the LOCAL model [15], one cannot hope to prove desirable approximation ratios for a $Q$ of max-degree $\mathrm{poly}(1/p)$ following this approach.

In this work, we demonstrate that it is possible to relax the requirement regarding the independent matching of endpoints of any non-crucial edge in $M_c$. Instead, we replace it with an upper bound on the variance of a parameter related to the neighborhood of each vertex. Specifically, it should be possible to pick a subset $A$ of the vertices unmatched by $M_c$ such that:

1. 1.

   Any non-crucial edge $e=(u,v)$ satisfies $\text{Pr}[\{u,v\}\subset A]\ge \delta$ for a fixed constant $\delta >0$.

2. 2.

   Let us define random variable $Z_v$ related to the neighborhood of any vertex $v$ as

   $$Z_v=\sum _{e=(u,v)\in N}\frac{x_e}{\text{Pr}[\{u,v\}\subset A]}{\mathrm{𝟙}}_{u\in A}.$$

   (1)

   Note that the randomization here is due to $A$ and $M_c$ being random variables themselves. We require the variance of this random variable to be upper-bounded as follows: $\mathrm{Var}(Z_v)\le \frac{10\tau }{{\delta }^2}.$

We define an algorithm for finding $M_c$ and $A$ to be a variance-bounding matching algorithm (see definition 10) if it satisfies the above-mentioned property (and a few others). We then provide a reduction demonstrating that if $M_c$ is an $\alpha$-approximation with respect to the contribution of crucial edges to the optimal solution, then it is possible to find an almost $\frac{1}{2-\alpha }$-approximate solution on the realized edges of $Q$. Our proof strongly relies on independent edge realizations, hence enabling us to break the $2/3$ barrier.

The second step of our analysis involves proving the existence of variance-bounding matching algorithms with approximation ratios of almost $0.535$ and $1-1/e$, respectively, for general graphs and bipartite graphs. In order to do this, we utilize algorithms designed for a variant of online stochastic matchings, particularly batched random-order contention resolution schemes (RCRS). We prove that any $\alpha$-selectable RCRS can be used to obtain a variance-bounding matching algorithm with an approximation ratio of almost $\alpha$. We discuss this in Section 6.

In the stochastic weighted matching problem, the input is an $n$-vertex graph $G=(V,E)$, a vector of weights $𝒘=\{w_e:e\in E\}$ and a probability vector $𝒑=\{p_e:p_e\in E\}$. Subgraph $𝒢$ is a random subgraph of $G$ which contains each edge independently with probability $p_e$. The goal in this problem is to pick a subgraph $Q$ of $G$ without the knowledge of its realization such that: (1) $Q$ has a small max-degree, namely a constant with respect to $n$, and (2) The realized edges of $Q$ (i.e., the graph $Q\cap 𝒢$) contain a large weight approximate matching. We define the approximation ratio as

where $𝒬=𝒢\cap Q$ is the realization of $Q$ and $\text{MWM}(.)$ is a deterministic algorithm returning a maximum weighted matching of a given graph, and $𝖶(M)={\sum }_{e\in M}{w}_e$ is a function returning the weight of a given matching $M$. We will use $\text{opt}=\text{MWM}(𝒢)$ to refer to the maximum matching of the actual realization. We may sometimes abuse notation and use opt to refer to its expected weight when it is clear from the context. Note that while opt is a random variable $\text{E}[𝖶(\text{opt})]$ is just a number. For any edge $e\in E$, we define

where the probability is taken over the randomization in $𝒢$. Similarly, for any vertex $v\in V$ we let $x_v=\text{Pr}[v\in \text{opt}]$ be the probability that $v$ is matched in opt. By the definition stated below, $𝒙$ is a fractional matching as each vertex joins opt w.p. at most one.

Throughout the paper, we use the notation $O_{\epsilon }(f(n))$ which means we have assumed $\epsilon$ to be a constant to calculate the complexity of $f(n)$. The max-degree of subgraph $Q$ we find in this paper depends on the smallest $p_e$ amongst all edges, which we refer to as $p$. In other words

In the following table, we list a set of variables and their values, which we will use throughout the paper. Values are defined as functions of $\epsilon \in (0,1)$, which is a sufficiently small constant, and $\delta \in (0,1)$, which we will introduce in Definition 10.

In this section, we state the concentration inequalities and some of the probabilistic tools that will be used throughout the paper.

As discussed previously in Section 2, to prove Theorem 1, we will show that $𝒬$ contains a $0.68$-approximate matching for general graphs and a $0.73$-approximate matching for bipartite graphs. Since $𝒬$ is the union of $t=O_{\epsilon }(1/p)$ matchings, this proves our main result. In Definition 10, we define variance-bounding matching algorithms. In Lemma 11, we prove that for any $\alpha \in (0,1)$ and a small enough constant $\epsilon >0$ existence of an $\alpha$-approximate variance-bounding algorithm implies $𝒬$ contains a $(\frac{1}{2-\alpha }-\epsilon )$-approximate matching. In Lemma 21, we prove the existence of variance-bounding matching algorithms with approximation ratios of $(0.535-6\sqrt{\delta })$ and $(1-1/e-6\sqrt{\delta })$, respectively, for general and bipartite graphs where $\delta \in (0,1)$ is a parameter in Definition 10. In Table 1, we choose $\delta ={\epsilon }^{0.5}$. By picking a sufficiently small enough $\epsilon$, this implies that $𝒬$ contains a matching with an approximation ratio of

for general graphs and approximation ratio of

for bipartite graphs.

In this section, we will construct a fractional matching on the non-crucial edges to augment the matching we get from running a variance-bounding matching on the crucial edges. Given a variance-bounding algorithm $𝒱ℬ$, let $M_c$ and $A$ be the output of $𝒱ℬ$ with inputs given according to Definition 12. To begin, let us define a variable $g_e$ for any non-crucial edge as follows:

where $x_e$ is defined as

Ideally, for constructing our fractional matching, we would assign a fractional value of $g_e$ to edge $e$ whenever $e\in 𝒬$ and both of its endpoints are in $A$. Since these events are independent due to Claim 13, their joint probability is $\text{Pr}[e\in 𝒬]\text{Pr}[u,v\in A]$. By constructing a fractional matching in this manner, we achieve $\text{E}[f_e]=x_e$ for any edge $e$ and $\text{E}[𝒇\cdot 𝒘]=\text{E}[𝖶(\text{opt})]$.

However, the challenge lies in the fact that constructing $𝒇$ in this way may result in it not being a valid fractional matching, as certain vertices may have a fractional degree greater than one. In other words, ${\sum }_{(u,v)\in N}{f}_{(u,v)}>1$ may occur for some vertices $v\in V$. To address this issue, we first scale down the fractional values by a small amount. Subsequently, we discard any vertex whose fractional degree still exceeds one. The challenge then becomes demonstrating that this event does not significantly reduce the expected size of the fractional matching. We formally state the algorithm for constructing a fractional matching on the non-crucial edges in Algorithm 2.

Since our ultimate goal is to demonstrate the existence of a large weight integral matching on $𝒬$ rather than a fractional one, let us first address the integrality gap of the fractional matching produced by this algorithm. We first prove an upper bound of ${\epsilon }^3$ for $g_e$ of non-crucial edges in Claim 14. We then use this in Lemma 15 to prove that the output of Algorithm 2 has a small integrality gap. To help with the flow of the paper, both proofs are deferred to the full version.

Let ${𝒇}^{\mathbf{\prime }}$ denote the value of $𝒇$ constructed by Algorithm 2 before it zeroes out certain $f_e$ values in Line 13. As discussed earlier in this section, it is evident that $\text{E}[f_e^{\prime }]=\gamma x_e$ for any edge in $e\in N$. Since $\gamma$ deviates from one by a small constant, the expected weight of ${𝒇}^{\mathbf{\prime }}$ is a sufficiently large approximation relative to the contribution of the non-crucial edges to the optimal solution. Thus, the primary challenge lies in proving that we do not incur a substantial loss by zeroing out certain $f_e$ values in Line 13. Roughly speaking, we only have the opportunity to use an edge $e=(u,v)$ whenever it is in $𝒬$ and its endpoints are in $A$ (i.e., $f_e^{\prime }\ne 0)$, and we lose this opportunity if at least one of its endpoints does not survive Algorithm 2. That is, we have:

To quantify the amount of loss per edge, we need to upper-bound $\text{Pr}[u\text{ or }v\text{ do not survive }\mid f_e^{\prime }\ne 0]$ and show that it is significantly smaller compared to $\text{Pr}[f_e^{\prime }\ne 0]$. Note that here, $f_e^{\prime }\ne 0$ is not independent of $e$’s end-points surviving since it contributes to their fractional degree. Furthermore, $e\in Q$ is correlated, albeit negatively (see Claim 25), with the existence of its neighboring non-crucial edges in $Q$, which may also impact the fractional degrees of $u$ and $v$ in ${𝒇}^{\mathbf{\prime }}$. However, it is still helpful to first upper-bound the probability of $u$ and $v$ surviving without conditioning on $f_e^{\prime }\ne 0$. The intuition behind this is that since $f_e^{\prime }$ is very small (i.e., upper-bounded by ${\epsilon }^3$ due to Claim 14), its impact on the fractional degree of each endpoint is insignificant. Moreover, since $e\in Q$ is negatively associated with $e^{\prime }\in Q$ for any non-crucial $e^{\prime }\ne e$ connected to $u$ or $v$, conditioning on $e\in Q$ does not increase their $f_{e^{\prime }}^{\prime }$. To upper-bound $\text{Pr}[v\text{ does not survive}]$ for any vertex $v$, let us define

Since we set $f_e^{\prime }=g_e\gamma$ iff $e\in Q$ and $\{u,v\}\subset A$, whenever vertex $v$ is present in $A$ we have

Hence, vertex $v$ survive Algorithm 2 iff $Y_v/\gamma \le 1$. In Lemma 16, we prove that random variable $Y_v$ is concentrated around its mean for any vertex. This analysis crucially relies on Property 4 of variance-bounding algorithms. This would have been enough if we knew $\text{E}[Y_v]$ is sufficiently close to one. While we do not exactly have this, we can use the second property of the variance-bounding algorithms to show $\text{E}[Y_v|v\in A]\le 1$. This is only doable thanks to Property 2. Combining all these together, we are able to finally prove in Lemma 17 that $Y_v$ is sufficiently close to one, with a sufficiently large portability.

Since both Lemma 16 and Lemma 17 have lengthy and technical proofs, we respectively allocate Section A.1 and another section in the full version to present detailed proofs for them. Finally, we put the pieces together in Lemma 20 to demonstrate that $\text{E}[f_e]$ is sufficiently large compared to $x_e$ (the contribution of $e$ to the optimal solution).

The proof is deferred to the full version of the paper.

Due to space constraints, we defer the proof of these two lemmas to the full version.

In this section, we will put all the pieces together to formally prove Lemma 11. Let $Q$ be the subgraph outputted by Algorithm 1. We prove that the existence of an $\alpha$-approximation variance-bounding matching algorithm means $𝒬$, the realization of $Q$, contains a $\frac{1}{2-\alpha }-\epsilon$ approximate solution. Since $Q$ is the union of $t=\frac{1}{\tau \epsilon }$ matchings, plugging in the value of $\tau =p{\epsilon }^5{\delta }^2$ from Table 1 implies $Q$ has max-degree $O_{\epsilon }(1/p)$. Therefore, to prove this lemma, it suffices to show that $𝒬$ contains a $\frac{1}{2-\alpha }-\epsilon$ approximate solution.

Let $M_c$ and $A$ be the outputs of the $\alpha$-approximation variance-bounding algorithm on inputs specified in Definition 12. Recall that $M_c$ is a matching on the crucial edges and $A$ is a subset of vertices unmatched in $M_c$. Let $\sigma$ be the ratio of the optimal solution that comes from the crucial edges. That is

Due to Claim 13, we know that the expected weight of $M_c$ is $\alpha \sigma$ fraction of the optimal solution. Furthermore, we showed in Claim 8 that any crucial edge belongs to $Q$ with probability at least $(1-\epsilon )$. As a result we have

The next step is to use the non-crucial edges among vertices in $A$ to augment $M_c\cap 𝒬$. In Lemma 20, we prove that it is possible to construct a fractional matching $𝒇$ on the non-crucial edges among vertices in $A$ such that for any non-crucial edge

Hence, $\text{E}[𝒇𝒘]\ge (1-\sigma )(1-\epsilon /2)𝖶(\text{opt}).$ As a result of Lemma 15 it is possible to round $𝒇$ and achieve an integral matching $M_n$ such that

Putting Equation 5 and Equation 6 together implies the existence of a matching in $𝒬$ with expected weight at least

We claim that the best of this matching and simply taking the max-weight matching among the crucial edges of $𝒬$ gives us the desired approximating ratio. Since each crucial edge belongs to $Q$ w.p. at least $1-\epsilon$, its realization contains a matching with expected weight at least $(1-\epsilon )$ times the contribution of crucial edges to the optimal solution which is $(1-\epsilon )\sigma 𝖶(\text{opt}).$ The best of these two solutions gives us the approximation ratio of at least

Hence, this implies that the realization of subgraph $Q$ with max-degree $O_{\epsilon }(1/p)$ contains a $(\frac{1}{2-\alpha }-\epsilon )$- approximate solution completing the proof of Lemma 11.