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.
|Title of host publication||Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing|
|Place of Publication||New York, NY, USA|
|Number of pages||10|
|Publication status||Published - 2005|
- approximate counting
- contingency tables
- integral flows