I was making my way through the paper by Jerrum, Sinclair, and Vigoda on developing a randomized polynomial time procedure (FRPAS) for approximating the permanent of a matrix $A$ with non-negative entries. The paper mainly argues with the case when the entries of $A$ are in $\{0,1 \}$ and aims to approximate the number of perfect matchings of the bipartite graph $G = (V, E)$ with adjacency matrix $$\begin{bmatrix}0&A \\ A^{T}&0 \end{bmatrix}.$$

The paper does this by introducing a Markov chain with sample space $\Omega = \mathcal{M} \cup_{u,v \in V} \mathcal{M}(u,v)$ where $\mathcal{M}$ is the set of perfect matchings and $\mathcal{M}(u,v)$ is the set of "near perfect" matchings, these are matchings that cover all the vertices except the vertices $u$ and $v$. The Markov chain proceeds from a state $M$ either to state $M'$ or remains at state $M$

The transition rule and state $M'$ is given on pg 678 of the work. I'm having trouble understanding the case where if you are at a state $M \in \mathcal{M}(u,v)$, in particular, the cases 2ii and 2iii.

It says that if you are at a state $M \in \mathcal{M}(u,v)$ then you choose $z$ uniformly from $V = V_{1} \cup V_{2}$. If $z \notin \{u, v \}$ then $z \in V_{1}$ or $z \in V_{2}$. For example, if $z \in V_{1}$ and the edge $(z,v) \in E$ then $M' = M \cup (z,v) \setminus (z,y).$

I just don't understand what $y$ is here?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.