Enumerating contingency tables via random permanents
| dc.creator | Barvinok, Alexander | |
| dc.date | 2005-11-23 | |
| dc.date | 2006-03-07 | |
| dc.date.accessioned | 2026-07-07T06:51:40Z | |
| dc.date.available | 2026-07-07T06:51:40Z | |
| dc.description | Given m positive integers R=(r_i), n positive integers C=(c_j) such that sum r_i = sum c_j =N, and mn non-negative weights W=(w_{ij}), we consider the total weight T=T(R, C; W) of non-negative integer matrices (contingency tables) D=(d_{ij}) with the row sums r_i, column sums c_j, and the weight of D equal to prod w_{ij}^{d_{ij}}. We present a randomized algorithm of a polynomial in N complexity which computes a number T'=T'(R,C; W) such that T' < T < alpha(R, C) T' where alpha(R,C) = min{prod r_i! r_i^{-r_i}, prod c_j! c_j^{-c_j}} N^N/N!. In many cases, ln T' provides an asymptotically accurate estimate of ln T. The idea of the algorithm is to express T as the expectation of the permanent of an N x N random matrix with exponentially distributed entries and approximate the expectation by the integral T' of an efficiently computable log-concave function on R^{mn}. Applications to counting integer flows in graphs are also discussed. | |
| dc.description | 19 pages, bounds are sharpened, references are added | |
| dc.identifier | https://arxiv.org/abs/math/0511596 | |
| dc.identifier | http://arxiv.org/abs/math/0511596 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/105065 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.subject | 05A16, 68R05, 60C05 | |
| dc.title | Enumerating contingency tables via random permanents | |
| dc.type | text |