Heng Cao, Haifeng Xi, et al.
WSC 2003
We consider the problem of computing the permanent of a 0, 1 n by n matrix. For a class of matrices corresponding to constant degree expanders we construct a deterministic polynomial time approximation algorithm to within a multiplicative factor (1 + ε)n, for arbitrary ε > 0. This is an improvement over the best known approximation factor en obtained in Linial, Samorodnitsky and Wigderson (2000) [9], though the latter result was established for arbitrary non-negative matrices. Our results use a recently developed deterministic approximation algorithm for counting partial matchings of a graph (Bayati, Gamarnik, Katz, Nair and Tetali (2007) [2]) and Jerrum-Vazirani method (Jerrum and Vazirani (1996) [8]) of approximating permanent by near perfect matchings. © 2010 Elsevier Inc. All rights reserved.
Heng Cao, Haifeng Xi, et al.
WSC 2003
Peter Wendt
Electronic Imaging: Advanced Devices and Systems 1990
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989
Y.Y. Li, K.S. Leung, et al.
J Combin Optim