= Dense permanent approximation
{title2=$\delta(G)>n/2\Longrightarrow\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$.
Back to article page
