Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
复制标题
用于近似简单指数因子内的常量和混合判别式的多项式时间算法
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
A. Barvinok
中科院分区：
文献类型：
--
作者：
A. Barvinok
我们提出了真实的，复杂的，和四元数版本的一个简单的随机多项式时间算法近似永久的非负矩阵，更一般地说，混合判别式的半正定矩阵。该算法提供了一个无偏估计，它以高概率在O（cn）的因子内近似真实值，其中n是矩阵的大小，其中c = 0.28（对于真实的版本），c = 0.56（对于复数版本），c = 0.76（对于四元数版本）。我们讨论了我们的方法的可能扩展以及混合判别式在组合计数问题中的应用。©1999 John Wiley & Sons，Inc. Random Struct. Alg.，1999年第14、29-61号来文
We present real, complex, and quaternionic versions of a simple randomized polynomial time algorithm to approximate the permanent of a nonnegative matrix and, more generally, the mixed discriminant of positive semidefinite matrices. The algorithm provides an unbiased estimator, which, with high probability, approximates the true value within a factor of O(cn), where n is the size of the matrix (matrices) and where c ≈ 0.28 for the real version, c ≈ 0.56 for the complex version, and c ≈ 0.76 for the quaternionic version. We discuss possible extensions of our method as well as applications of mixed discriminants to problems of combinatorial counting. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 29–61, 1999