An analysis of Monte Carlo algorithm for estimating the permanent

DOI10.1007/BF01294460MaRDI QIDQ1842570zbMATH OpenOpenAlexWikidataFDO

Authors Alan Frieze, Mark Jerrum

Publication date 23 July 1995

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01294460

zbMATH Keywords

Monte Carlo algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A Monte-Carlo Algorithm for Estimating the Permanent
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Approximating the Permanent

Cites work

• scientific article; zbMATH DE number 1003265 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3747179 (Why is no real title available?)
• scientific article; zbMATH DE number 3311772 (Why is no real title available?)
• A Monte-Carlo Algorithm for Estimating the Permanent
• Approximating the Permanent
• Approximating the permanent: A simple approach
• Counting the Number of Hamilton Cycles in Random Digraphs
• Highly resilient correctors for polynomials
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• On coupling and the approximation of the permanent
• Random generation of combinatorial structures from a uniform distribution
• Some Theorems on Abstract Graphs
• The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph
• The complexity of computing the permanent

Cited in

(18)

• A Monte-Carlo Algorithm for Estimating the Permanent
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• Singular values of Gaussian matrices and permanent estimators
• Estimating the permanent by importance sampling from a finite population
• Approximating the  -permanent
• scientific article; zbMATH DE number 3954144 (Why is no real title available?)
• Clifford algebras and approximating the permanent
• Matrix permanent and quantum entanglement of permutation invariant states
• Approximating the permanent: A simple approach
• A mildly exponential approximation algorithm for the permanent
• Approximately counting embeddings into random graphs
• scientific article; zbMATH DE number 4082843 (Why is no real title available?)
• Counting the Number of Hamilton Cycles in Random Digraphs
• Monte Carlo algorithms for computing \(\alpha \)-permanents
• A load balancing strategy for parallel computation of sparse permanents.
• Approximating the Permanent
• Random path method with pivoting for computing permanents of matrices
• Perfect matchings and derangements on graphs

This page was built for publication: An analysis of Monte Carlo algorithm for estimating the permanent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1842570)