Approximately Counting Integral Flows and Cell-bounded Contingency Tables

Mary Cryan, Martin Dyer, Dana Randall

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the problem of approximately counting integral flows in a network. We show that there is an fpras based on volume estimation if all capacities are sufficiently large, generalising a result of Dyer, Kannan and Mount (1997). 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 generalises an algorithm of Cryan and Dyer (2002) for standard contingency tables, but the analysis here is considerably more intricate.
Original languageEnglish
Title of host publicationProceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing
Place of PublicationNew York, NY, USA
PublisherACM
Pages413-422
Number of pages10
ISBN (Print)1-58113-960-8
DOIs
Publication statusPublished - 2005

Publication series

NameSTOC '05
PublisherACM

Keywords

  • approximate counting
  • contingency tables
  • integral flows

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

Cite this