A Mildly Exponential Approximation Algorithm for the Permanent

An approximation algorithm for the permanent of an n*n 0, 1-matrix is presented. The algorithm is shown to have worst-case time complexity exp (0(n/sup 1/2/ log/sup 2/ n)). Asymptotically, this represents a considerable improvement over the best existing algorithm, which has worst-case time complexity of the form e/sup theta (n)/. >

Authors

• Mark Jerrum
• Umesh V. Vazirani

Keywords

• Approximation algorithms
• Computer science
• Bipartite graph
• Mathematics
• NP-hard problem
• Turing machines
• Polynomials
• Random variables
• Monte Carlo methods
• Markov Chain
• Time Complexity
• Estimation Algorithm
• Reachable
• Perfect Match
• Estimation Strategy
• Vertices
• Exact Algorithm
• Expansion Factor
• Worst-case Complexity
• Expansion Ratio
• Incident Edges
• Department Of Computer Science
• Worst-case Time Complexity