An approximation algorithm for counting contingency tables

Alexander Barvinok, Zur Luria, Alex Samorodnitsky, Alexander Yong

Research output: Contribution to journalArticle

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 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.

Original languageEnglish (US)
Pages (from-to)25-66
Number of pages42
JournalRandom Structures and Algorithms
Volume37
Issue number1
DOIs
StatePublished - Aug 1 2010

Keywords

  • Contingency tables
  • Matrix scaling
  • Permanent approximation
  • Randomized algorithms

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'An approximation algorithm for counting contingency tables'. Together they form a unique fingerprint.

  • Cite this