Approximating the Permanent

Lars Eilstrup Rasmussen

Abstract: In this paper we present an efficient and very simple unbiased estimator for the Permanent of square (0-1) matrices. As the main result, we prove that our estimator, even though its worst case behaviour is provably very bad, runs in time polynomial in the size of the input matrix for almost all matrices. We also generalise our technique and apply it to another enumeration problem, that of counting Hamilton cycles in directed graphs. The ease with which this was done suggests that the basic technique may have wide applicability.

LFCS report ECS-LFCS-92-201

Previous | Index | Next