An analysis of Monte Carlo algorithm for estimating the permanent

DOI10.1007/BF01294460zbMath0817.68087OpenAlexW2908728486WikidataQ57401567 ScholiaQ57401567MaRDI QIDQ1842570

Mark R. Jerrum, Alan M. Frieze

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)

Related Items

Singular values of Gaussian matrices and permanent estimators, Random path method with pivoting for computing permanents of matrices, Counting the Number of Hamilton Cycles in Random Digraphs, A mildly exponential approximation algorithm for the permanent, Perfect matchings and derangements on graphs, Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor, Estimating the permanent by importance sampling from a finite population, Clifford algebras and approximating the permanent, Approximately Counting Embeddings into Random Graphs, Matrix permanent and quantum entanglement of permutation invariant states, A load balancing strategy for parallel computation of sparse permanents

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• Random generation of combinatorial structures from a uniform distribution
• On coupling and the approximation of the permanent
• Highly resilient correctors for polynomials
• Approximating the Permanent
• Counting the Number of Hamilton Cycles in Random Digraphs
• A Monte-Carlo Algorithm for Estimating the Permanent
• Approximating the permanent: A simple approach
• The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph
• Some Theorems on Abstract Graphs