Mathematics – Combinatorics
Scientific paper
2005-03-08
Mathematics
Combinatorics
16 pages
Scientific paper
We represent the number of mxn non-negative integer matrices (contingency tables) with prescribed row sums and column sums as the expected value of the permanent of a non-negative random matrix with exponentially distributed entries. We bound the variance of the obtained estimator, from which it follows that if the row and column sums are bounded by a constant fixed in advance, we get a polynomial time approximation scheme for counting contingency tables. We show that the complete symmetric polynomial of a fixed degree in n variables can be epsilon-approximated coefficient-wise by a sum of powers of O(log n) linear forms, from which it follows that if the row sums (but not necessarily column sums) are bounded by a constant, there is a deterministic approximation algorithm of m^{O(log n)} complexity to compute the logarithmic asymptotic of the number of tables.
No associations
LandOfFree
Low rank approximations of symmetric polynomials and asymptotic counting of 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 Low rank approximations of symmetric polynomials and asymptotic counting of contingency tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low rank approximations of symmetric polynomials and asymptotic counting of contingency tables will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-369695