Informatics Report Series


Report   

EDI-INF-RR-0466


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:A Polynomial-Time Algorithm to Approximately Count Contingency Tables when the Number of Rows is Constant
Authors: Mary Cryan ; Martin Dyer
Date:Sep 2003
Publication Title:Journal of Computer and System Sciences
Publisher:Elsevier
Publication Type:Journal Article Publication Status:Published
Volume No:67(2) Page Nos:291-310
DOI:10.1016/S0022-0000(03)00014-X
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},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh