Wavefront and caustic surfaces of refractive laser beam shaper
David L. Shealy, John A. Hoffnagle
SPIE Optical Engineering + Applications 2007
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.
David L. Shealy, John A. Hoffnagle
SPIE Optical Engineering + Applications 2007
Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems
R.A. Brualdi, A.J. Hoffman
Linear Algebra and Its Applications
Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998