@inproceedings{bd7bb3cc48b7467685e32bfb91496ec2,

title = "Approximately Counting Integral Flows and Cell-bounded Contingency Tables",

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

keywords = "approximate counting, contingency tables, integral flows",

author = "Mary Cryan and Martin Dyer and Dana Randall",

year = "2005",

doi = "10.1145/1060590.1060652",

language = "English",

isbn = "1-58113-960-8",

series = "STOC '05",

publisher = "ACM",

pages = "413--422",

booktitle = "Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing",

}