Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor

作     者：Barvinok, A 

作者机构：Univ Michigan Dept Math Ann Arbor MI 48109 USA 

出 版 物：《RANDOM STRUCTURES & ALGORITHMS》 (随机结构和算法)

年 卷 期：1999年第14卷第1期

页      面：29-61页

核心收录：

学科分类：07[理学] 0835[工学-软件工程] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：permanent mixed discriminant randomized algorithms approximation algorithms 

摘      要：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(c(n)), where n is the size of the matrix (matrices) and where c approximate to 0.28 for the real version, c approximate to 0.56 for the complex version, and c approximate to 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. (C) 1999 John Wiley & Sons, Inc.