Enumeration of contingency tables and integer flows

by Alexander Barvinok

We consider the problem of efficient enumeration of contingency tables
(non-negative integer matrices with prescribed row and column sums) as well
as the more general problem of enumeration of integer flows in a network
with prescribed excesses at the vertices. We show that the number of
contingency tables (integer flows) is well-approximated by the integral
of an efficiently computable log-concave density, which leads to
approximation algorithms in the above problems as well as to a version
of the Brunn-Minkowski inequality for the number of contingency tables
as a function of the margins and for the number of integer flows as a
function of the excesses at the vertices .