An approximation algorithm for counting contingency tables |
| |
Authors: | Alexander Barvinok Zur Luria Alex Samorodnitsky Alexander Yong |
| |
Institution: | 1. Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109‐1043;2. Department of Computer Science, Hebrew University of Jerusalem, Givat Ram Campus, 91904, Israel;3. Department of Mathematics, University of Illinois at Urbana‐Champaign, Urbana, Illinois 61801 |
| |
Abstract: | We present a randomized approximation algorithm for counting contingency tables, m × n non‐negative integer matrices with given row sums R = (r1,…,rm) and column sums C = (c1,…,cn). We define smooth margins (R,C) in terms of the typical table and prove that for such margins the algorithm has quasi‐polynomial NO(ln N) complexity, where N = r1 + … + rm = c1 + … + cn. 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 + )/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. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010 |
| |
Keywords: | contingency tables randomized algorithms matrix scaling permanent approximation |
|
|