Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
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.
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
Alfred K. Wong, Antoinette F. Molless, et al.
SPIE Advanced Lithography 2000
David L. Shealy, John A. Hoffnagle
SPIE Optical Engineering + Applications 2007
Peter Wendt
Electronic Imaging: Advanced Devices and Systems 1990