A Polynomial-time Algorithm to Approximately Count Contingency Tables when the Number of Rows is Constant

Mary Cryan, Martin Dyer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the problem of counting the number of contingency tables with given row and column sums. This problem is known to be #P-complete, even when there are only two rows [7]. In this paper we present the first fully-polynomial randomized approximation scheme for counting contingency tables when the number of rows is constant. A novel feature of our algorithm is that it is a hybrid of an exact counting technique with an approximation algorithm, giving two distinct phases. In the first, the columns are partitioned into "small" and "large". We show that the number of contingency tables can be expressed as the weighted sum of a polynomial number of new instances of the problem, where each instance consists of some new row sums and the original large column sums. In the second phase, we show how to approximately count contingency tables when all the column sums are large. In this case, we show that the solution lies in approximating the volume of a single convex body, a problem which is known to be solvable in polynomial time [5].
Original languageEnglish
Title of host publicationProceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing
Place of PublicationNew York, NY, USA
PublisherACM
Pages240-249
Number of pages10
ISBN (Print)1-58113-495-9 doi
DOIs
Publication statusPublished - 2002

Publication series

NameSTOC '02
PublisherACM

Fingerprint

Dive into the research topics of 'A Polynomial-time Algorithm to Approximately Count Contingency Tables when the Number of Rows is Constant'. Together they form a unique fingerprint.

Cite this