A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix
A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix
复制标题
计算 0,1 矩阵常量的确定性近似算法
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Dmitriy A. Katz
中科院分区：
文献类型：
--
作者：
D. Gamarnik;Dmitriy A. Katz
我们构造了一个确定性的近似算法，用于计算一个0，1 $n$乘$n$矩阵的积和式在一个乘法因子$（1+ n）^n$内，对于任意的$n>0$。当矩阵下的图是一个常数度扩展器时，我们的算法在多项式时间（PTAS）内运行。在一般情况下，算法的运行时间是$exp（O（n^{2 over 3}log^3n））$。对于常度扩张图类，第一个结果是对文献[LinialSamorodnitskyWigderson]中最好的逼近因子e^n的改进.
我们的结果使用最近开发的确定性近似算法计算图Bayati等人的部分匹配，和Jerrum-Vazirani分解方法。
We construct a deterministic approximation algorithm for computing a permanent of a $0,1$ $n$ by $n$ matrix to within a multiplicative factor $(1+epsilon)^n$, for arbitrary $epsilon>0$. When the graph underlying the matrix is a constant degree expander our algorithm runs in polynomial time (PTAS). In the general case the running time of the algorithm is $exp(O(n^{2over 3}log^3n))$. For the class of graphs which are constant degree expanders the first result is an improvement over the best known approximation factor $e^n$ obtained in cite{LinialSamorodnitskyWigderson}.
Our results use a recently developed deterministic approximation algorithm for counting partial matchings of a graph Bayati et al., and Jerrum-Vazirani decomposition method.