An approximation algorithm for counting contingency tables

Details An approximation algorithm for counting contingency tables An approximation algorithm for counting contingency tables

2008-03-27

arxiv.org/abs/0803.3948v1

Random Structures Algorithms 37 (2010), no. 1, 25-66

Mathematics

Combinatorics

45 pages

Scientific paper

We present a randomized approximation algorithm for counting contingency tables, mxn non-negative integer matrices with given row sums R=(r_1, ..., r_m) and column sums C=(c_1, ..., c_n). We define smooth margins (R,C) in terms of the typical table and prove that for such margins the algorithm has quasi-polynomial N^{O(ln N)} complexity, where N=r_1+...+r_m=c_1+...+c_n. Various classes of margins are smooth, e.g., when m=O(n), n=O(m) and the ratios between the largest and the smallest row sums as well as between the largest and the smallest column sums are strictly smaller than the golden ratio (1+sqrt{5})/2 = 1.618. The algorithm builds on Monte Carlo integration and sampling algorithms for log-concave densities, the matrix scaling algorithm, the permanent approximation algorithm, and an integral representation for the number of contingency tables.

Affiliated with

Also associated with

No associations

Rating

An approximation algorithm for counting contingency tables does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An approximation algorithm for counting contingency tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An approximation algorithm for counting contingency tables will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-354093