Robert F. Gordon, Edward A. MacNair, et al.
WSC 1985
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.
Robert F. Gordon, Edward A. MacNair, et al.
WSC 1985
Alfred K. Wong, Antoinette F. Molless, et al.
SPIE Advanced Lithography 2000
Y.Y. Li, K.S. Leung, et al.
J Combin Optim
Yi Zhou, Parikshit Ram, et al.
ICLR 2023