# A C++ code to compute bounds for the permanent of a 0-1 matrix
by the ``average distance'' approach

This code, written by Eric Michael Ryckman, is a realization of
the algorithm suggested in
The distance approach to approximate combinatorial counting
by A. Samorodnitsky and A. Barvinok. Given an nxn matrix *A* of
0's and 1's, the algorithm interprets the permanent of *A* as the
number of perfect matchings in a bipartite graph *G* encoded by *A*.
The set *M* of all perfect matchings in *G* is embedded into
a Boolean
cube *C*_{m}={0,1}^{m}
(the algorithm tries to minimize the dimension
*m* of the cube). Then the algorithm computes (approximately) the
average Hamming distance from a point in *C*_{m} to the set
of perfect matchings in *G*. The distance is computed by averaging
distances to *M* from a number of randomly sampled points in
the cube *C*_{m}. The number of random points
to be sampled is determined
by the user and our experience shows that relatively few points are
needed to achieve a reasonably high precision (generally, we seem to have
to sample much fewer points than suggested by theoretical bounds of the
paper). For each particular point, the distance to the set of perfect
matchings *M* is computed by solving an appropriate Assignment
Problem. To solve the Assignment problem, with a kind permission of the
authors, we use the code of R. Jonker and A. Volgenant,
A shortest augmenting path algorithm for dense and sparse assignment
problem, *Computing*, **38** 1987, 325--340.
Based on the average distance from a random point *x* in the
Boolean cube *C*_{m} to the set of perfect matchings *M*
in *G*, the algorithm provides a lower and an upper
bound for the logarithm of the cardinality of *M*, which
is equal to the logarithm of the permanent of the
input matrix *A*. The bounds are
best possible in the following sense: if for some set *M* of points
in the cube *C*_{m} (not necessarily the set of perfect matchings
in a graph) the only information available is the average
Hamming distance from a random point *x* to *M*, one can't
provide better bounds. Quite possibly, the set of perfect
matchings in a graph has some special metric properties which we don't
know how to use yet. In any case, the algorithm outputs also the
average of the lower and the upper bounds and it has been our observation that
in many cases the true value of log_{2} per *A*
is close to that average.
The input matrix *A* should be stored in a file. It can be typed
using any text editor line by line with spaces between entries, such
as

0 1 1 0 1

1 0 1 1 0

0 1 0 1 1

1 1 0 0 1

1 1 1 1 1

The algorithm seems to be extremely fast, being able to handle 200x200
matrices in a matter of seconds. The produced permanent bounds are pretty
crude, yet often non-trivial (to get interesting results one should
apply the algorithm to matrices of a large size).

The source C++ code