- 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).
- Links To Paper
- This is the DOI link for the Journal webpage for this paper.
- Mary Cryan's webpage, where a .ps copy of the paper can be found.
- Bibtex format
- @Article{EDI-INF-RR-0466,
- author = {
Mary Cryan
and Martin Dyer
},
- title = {A Polynomial-Time Algorithm to Approximately Count Contingency Tables when the Number of Rows is Constant},
- journal = {Journal of Computer and System Sciences},
- publisher = {Elsevier},
- year = 2003,
- month = {Sep},
- volume = {67(2)},
- pages = {291-310},
- doi = {10.1016/S0022-0000(03)00014-X},
- url = {http://dx.doi.org/10.1016/S0022-0000(03)00014-X},
- }
|
