Dense permanent approximation ($\delta (G)>n/2⟹\text{a randomized relative approximation scheme}$)

If every row and column of an $n$-by-$n$ zero-one matrix has more than $n/2$ ones, its permanent of a matrix has a fully polynomial randomized approximation scheme. The short augmenting paths in a dense bipartite graph bound makes the leading coefficient dominate the matching generating function at polynomially large activity. The weighted matching Markov chain samples polynomially bounded activities in polynomial mixing time. Estimate successive annealing ratios for a matching generating function and divide by the final activity to the power $n$.