Low rank approximations of symmetric polynomials and asymptotic counting of contingency tables
Low rank approximations of symmetric polynomials and asymptotic counting of contingency tables
复制标题
对称多项式的低秩近似和列联表的渐近计数
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
A. Barvinok
中科院分区：
文献类型：
--
作者：
A. Barvinok
我们表示的数量mxn非负整数矩阵（列联表）与规定的行和和列和作为期望值的永久的非负随机矩阵的指数分布的项目。我们约束得到的估计量的方差，由此得出，如果行和列的总和是有界的一个常数事先固定，我们得到一个多项式时间近似计划计数列联表。我们证明了n个变量的固定次数的完全对称多项式可以通过O（log n）线性形式的幂和进行系数ε近似，由此得出，如果行和（但不一定是列和）由常数限制，则存在复杂性为m^{O（log n）}的确定性近似算法来计算表数的对数渐近。
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.