skip to main content
10.1145/1060590.1060652acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

Approximately counting integral flows and cell-bounded contingency tables

Published: 22 May 2005 Publication History

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]
A. Barvinok, A polynomial-time algorithm for counting integral points in polyhedra when the dimension is fixed, Mathematics of Operations Research 19, pp. 769--779, 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]
M. Cryan and M. Dyer, A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant, in Journal of Computer and System Sciences, 67(2): pp. 291--310, 2003.
[5]
M. Cryan, M. Dyer, L. Goldberg, M. Jerrum and R. Martin, Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows, in Proc. 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 711--720, 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]
M. Dyer, Approximate counting by dynamic programming, in Proc. 35th Annual ACM Symposium on the Theory of Computing, pp. 693--699, 2003.
[12]
M. Dyer and C. Greenhill, Polynomial-time counting and sampling of two-rowed contingency tables. Theoretical Computer Science 246, pp. 265--278, 2000.
[13]
M. Dyer, A. Frieze and R. Kannan, A random polynomial time algorithm for approximating the volume of convex bodies, Journal of the ACM 38, pp. 1--17, 1991.
[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]
M. Dyer, R. Kannan and J. Mount, Sampling contingency tables. Random Structures & Algorithms 10, pp. 487--506, 1997.
[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]
M. Jerrum, A. Sinclair and E. Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, in Proc. 33rd Annual ACM Symposium on Theory of Computing, pp. 712--721, 2001.
[19]
M. Jerrum, L. Valiant and V. Vazirani, Random generation of combinatorial structures from a uniform distribution, Theoretical Computer Science 43, pp. 169--188, 1986.
[20]
R. Kannan and S. Vempala, Sampling lattice points, in Proc. of 29th Annual ACM Symposium on Theory of Computing, pp. 696--700, 1997.
[21]
L. Lovász and S. Vempala, Simulated annealing in convex bodies and a O*(n4) volume algorithm, in Proc. 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 650--659, 2003.
[22]
B. Morris, Improved bounds for sampling contingency tables, in Random Structures & Algorithms, 21(2), pp. 135--146, 2002.
[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]
J. Mount, Fast unimodular counting, Combinatorics, Probability and Computing 9, pp. 277--285, 2000.
[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.

Cited By

View all
  • (2011)On the Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entriesJournal of Combinatorial Optimization10.1007/s10878-010-9323-922:3(457-468)Online publication date: 1-Oct-2011
  • (2010)Markov bases and subbases for bounded contingency tablesAnnals of the Institute of Statistical Mathematics10.1007/s10463-010-0289-262:4(785-805)Online publication date: 31-Mar-2010
  • (2009)On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded EntriesProceedings of the 15th Annual International Conference on Computing and Combinatorics10.1007/978-3-642-02882-3_31(307-316)Online publication date: 11-Jul-2009
  • Show More Cited By

Index Terms

  1. Approximately counting integral flows and cell-bounded contingency tables

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing
    May 2005
    778 pages
    ISBN:1581139608
    DOI:10.1145/1060590
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 22 May 2005

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. approximate counting
    2. contingency tables
    3. integral flows

    Qualifiers

    • Article

    Conference

    STOC05
    Sponsor:
    STOC05: Symposium on Theory of Computing
    May 22 - 24, 2005
    MD, Baltimore, USA

    Acceptance Rates

    Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

    Upcoming Conference

    STOC '25
    57th Annual ACM Symposium on Theory of Computing (STOC 2025)
    June 23 - 27, 2025
    Prague , Czech Republic

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 15 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2011)On the Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entriesJournal of Combinatorial Optimization10.1007/s10878-010-9323-922:3(457-468)Online publication date: 1-Oct-2011
    • (2010)Markov bases and subbases for bounded contingency tablesAnnals of the Institute of Statistical Mathematics10.1007/s10463-010-0289-262:4(785-805)Online publication date: 31-Mar-2010
    • (2009)On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded EntriesProceedings of the 15th Annual International Conference on Computing and Combinatorics10.1007/978-3-642-02882-3_31(307-316)Online publication date: 11-Jul-2009
    • (2008)Enumerating contingency tables via random permanentsCombinatorics, Probability and Computing10.1017/S096354830700866817:1(1-19)Online publication date: 1-Jan-2008

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media