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.

REFERENCES

• 1: S. Aoki, Exact methods and Markov chain Monte Carlo methods of conditional inference for contingency tables, PhD Thesis, University of Tokyo, 2004.
• 2: Alexander I. Barvinok, A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Mathematics of Operations Research, v.19 n.4, p.769-779, Nov. 1994
• 3: W. Baldoni-Silva, J. De Loera and M. Vergne, Counting integer flows in networks, 2003. Available from http://arxiv.org/abs/math/0303228.
• 4: Mary Cryan , Martin Dyer, A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant, Journal of Computer and System Sciences, v.67 n.2, p.291-310, September 2003 [doi>10.1016/S0022-0000(03)00014-X]
• 5: Mary Cryan , Martin E. Dyer , Leslie Ann Goldberg , Mark Jerrum , Russell A. Martin, Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.711-720, November 16-19, 2002
• 6: J. De Loera and B. Sturmfels, Algebraic unimodular counting, 2001. Available from http://arxiv.org/abs/math.CO/0104286.
• 7: P. Diaconis and B. Efron, Testing for independence in a two-way table: new interpretations of the chi-square statistic (with discussion), Annals of Statistics 13, pp. 845--913, 1995.
• 8: P. Diaconis and A. Gangolli, Rectangular arrays with fixed margins, in Discrete probability and algorithms (D. Aldous, P. Diaconis, J. Spencer and M. Steele, eds.), IMA Volumes on Mathematics and its Applications 72, Springer-Verlag, New York, pp. 15--41, 1995.
• 9: P. Diaconis and L. Saloff-Coste, Random walk on contingency tables with fixed row and column sums, Department of Mathematics, Harvard University, 1995.
• 10: P. Diaconis and B. Sturmfels, Algebraic algorithms for sampling from conditional distributions, Annals of Statistics 26, pp. 363--397, 1998.
• 11: Martin Dyer, Approximate counting by dynamic programming, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780643]
• 12: Martin Dyer , Catherine Greenhill, Polynomial-time counting and sampling of two-rowed contingency tables, Theoretical Computer Science, v.246 n.1-2, p.265-278, Sept 2000 [doi>10.1016/S0304-3975(99)00136-X]
• 13: Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
• 14: M. Dyer, A. Frieze, R. Kannan, A. Kapoor, L. Perkovic and U. Vazirani, A mildly exponential time algorithm for approximating the number of solutions to a multidimensional knapsack problem, Combinatorics, Probability and Computing 2, 271--284, 1993.
• 15: Martin Dyer , Ravi Kannan , John Mount, Sampling contingency tables, Random Structures & Algorithms, v.10 n.4, p.487-506, July 1997 [doi>10.1002/(SICI)1098-2418(199707)10:4<487::AID-RSA4>3.0.CO;2-Q ]
• 16: M. Grötschel, L. Lovász and A. Schrijver, Geometric algorithms and combinatorial optimization, Springer-Verlag, 1991.
• 17: R. Holmes and L. Jones, On uniform generation of two-way tables with fixed margins and the conditional volume test of Diaconis and Efron, Annals of Statistics 24, pp. 64--68, 1996.
• 18: Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.712-721, July 2001, Hersonissos, Greece [doi>10.1145/380752.380877]
• 19: M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
• 20: Ravi Kannan , Santosh Vempala, Sampling lattice points, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.696-700, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258665]
• 21: László Lovász , Santosh Vempala, Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.650, October 11-14, 2003
• 22: Ben J. Morris, Improved bounds for sampling contingency tables, Random Structures & Algorithms, v.21 n.2, p.135-146, September 2002 [doi>10.1002/rsa.10049]
• 23: J. Mount, Application of convex sampling to optimization and contingency table generation, PhD thesis, Carnegie Mellon University, 1995. (Technical Report CMU-CS-95-152, Department of Computer Science.)
• 24: John Mount, Fast Unimodular Counting, Combinatorics, Probability and Computing, v.9 n.3, p.277-285, May 2000 [doi>10.1017/S0963548300004193]
• 25: F. Rapollo, Markov bases and structural zeros. Preprint, Department of Mathematics, University of Genova, 2004.
• 26: A. Schrijver, Combinatorial optimization--polyhedra and efficiency, Springer-Verlag, Berlin, 2003.
• 27: L. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8, 189--201, 1979.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
approximate counting, contingency tables, integral flows