An Approximation Algorithm for Counting Contingency Tables
We present a randomized approximation algorithm for counting contingency tables, m x n non-negative integer matrices with given row sums R = (r(1), ... , r(m)) and column sums C = (c(1), ... , 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(In N)) complexity, where N = r(1) + ... + r(m) = c(1) + ... + 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 well as between the largest and the smallest column sums are strictly smaller than the golden ratio (1 + root 5)/2 approximate to 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. (C) 2010 Wiley Periodicals, Inc. Random Struct. Alg., 37, 25-66, 2010
contingency tables matrix scaling permanent approximation randomized algorithms