Approximately Counting Integral Flows and Cell-Bounded Contingency Tables

Mary Cryan, Martin Dyer, Dana Randall

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of approximately counting integral flows in a network. We show that there is a fully polynomial randomized approximation scheme (FPRAS) based on volume estimation if all capacities are sufficiently large, generalizing a result of Dyer, Kannan, and Mount [Random Structures Algorithms, 10 (1997), pp. 487–506]. We apply this to approximating the number of contingency tables with prescribed cell bounds when the number of rows is constant, but the row sums, column sums, and cell bounds may be arbitrary. We provide an FPRAS for this problem via a combination of dynamic programming and volume estimation. This generalizes an algorithm of Cryan and Dyer [J. Comput. System Sci., 67 (2003), pp. 291–310] for standard contingency tables, but the analysis here is considerably more intricate.

Read More: http://epubs.siam.org/doi/abs/10.1137/060650544
Original languageEnglish
Pages (from-to)2683-2703
Number of pages21
JournalSIAM Journal on Computing
Volume39
Issue number7
DOIs
Publication statusPublished - 1 May 2010

Keywords / Materials (for Non-textual outputs)

  • approximate counting
  • cell-bounded contingency tables
  • lattice points
  • polytope
  • sampling

Fingerprint

Dive into the research topics of 'Approximately Counting Integral Flows and Cell-Bounded Contingency Tables'. Together they form a unique fingerprint.

Cite this