APPROXIMATING THE PERMANENT - A SIMPLE APPROACH

In this article, we present an efficient and very simple unbiased esti mator for the Permanent of square (0-1) matrices. As the main result, we prove that our estimator, even though its worst case behavior is pr ovably very bad, runs in time polynomial in the size of the input matr ix for almost all matrices. We also generalize our technique and apply it to another enumeration problem, that of counting Hamilton cycles i n directed graphs. The ease with which this was done suggests that the basic technique may have wide applicability. (C) 1994 John Wiley & So ns, Inc.