A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant

DOI10.1016/S0022-0000(03)00014-XzbMath1072.68127OpenAlexW4253228418WikidataQ56323948 ScholiaQ56323948MaRDI QIDQ5917580

Martin Dyer, Mary Cryan

Publication date: 18 November 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(03)00014-x

zbMATH Keywords

Randomized algorithmsContingency tablesApproximate counting

Mathematics Subject Classification ID

Contingency tables (62H17) Randomized algorithms (68W20)

Related Items

Power analysis of independence testing for three-way contingency tables of small sizes, Some contributions to practice of 2 × 2 contingency tables, Sequential Monte Carlo for counting vertex covers in general graphs, On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries, On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \), On the Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entries, A faster FPTAS for counting two-rowed contingency tables, An approximation algorithm for counting contingency tables, Enumerating Contingency Tables via Random Permanents, An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums, Random sampling of contingency tables via probabilistic divide-and-conquer

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing for independence in a two-way table: New interpretations of the chi-square statistic
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• Random generation of combinatorial structures from a uniform distribution
• Approximate counting, uniform generation and rapidly mixing Markov chains
• An application of Harnack inequalities to random walk on nilpotent quotients
• Polynomial-time counting and sampling of two-rowed contingency tables
• Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Sampling contingency tables
• Random walks and anO*(n5) volume algorithm for convex bodies
• On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• [https://portal.mardi4nfdi.de/wiki/Publication:4705324 Random generation of 2�n contingency tables]
• On sampling with Markov chains