On Complexity of Computing the Permanent of a Rectangular Matrix

摘要

We show that the permanent of an m x n rectan- gular matrix can becomputed with O(n2~m + 3~m ) multiplications and additions.Asymptotically, this is better than straightfor- ward extensions ofthe best known algorithms for the permanent of a square matrix whenm/n < log_32 and n→∞.