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
Read More: http://epubs.siam.org/doi/abs/10.1137/060650544
Original language | English |
---|---|
Pages (from-to) | 2683-2703 |
Number of pages | 21 |
Journal | SIAM Journal on Computing |
Volume | 39 |
Issue number | 7 |
DOIs | |
Publication status | Published - 1 May 2010 |
Keywords / Materials (for Non-textual outputs)
- approximate counting
- cell-bounded contingency tables
- lattice points
- polytope
- sampling