Let A be an n × n matrix with 0-1 valued entries, and let per(A) be the permanent of A. This paper describes a Monte-Carlo algorithm that produces a “good in the relative sense” estimate of per(A) and has running time poly(n)2^n / 2, where poly(n) denotes a function that grows polynomially with n.
No takes yet. Share an insight, caveat, or question.
Karmarkar et al. (1993) studied this question.
Synapse has enriched 4 closely related papers on similar clinical questions. Consider them for comparative context: