An approximation algorithm for counting contingency tables

We present a randomized approximation algorithm for counting contingency tables, m × n non-negative integer matrices with given row sums R = (r₁,...,r_m)and column sums C = (c₁,...,c_n). We define smooth margins (R,C) in terms of the typical table and prove that for such margins the algorithm has quasi-polynomial N^{O(ln N)} complexity, where N = r₁ + + r_m = c₁ + +c_n. Various classes of margins are smooth, e.g., when m = O(n), n = O(m) and the ratios between the largest and the smallest row sums as we√l as between the largest and the smallest column sums are strictly smaller than the golden ratio (1 + √ 5)/2 ≈ 1.618. The algorithm builds on Monte Carlo integration and sampling algorithms for log-concave densities, the matrix scaling algorithm, the permanent approximation algorithm, and an integral representation for the number of contingency tables.