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

Mary Cryan, Martin E. Dyer

Research output: Contribution to journalArticlepeer-review

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 (Random Structures Algorithms 10(4) (1997) 487). 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 (J. ACM 38 (1) (1991) 1).
Original languageUndefined/Unknown
Pages (from-to)291-310
Number of pages20
JournalJournal of Computer and System Sciences
Volume67
Issue number2
DOIs
Publication statusPublished - 2003

Cite this