A Monte-Carlo Algorithm for Estimating the Permanent
From MaRDI portal
Publication:4032938
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Recommendations
- An analysis of Monte Carlo algorithm for estimating the permanent
- Approximating the permanent: A simple approach
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- scientific article; zbMATH DE number 3930346
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
Cited in
(35)- Computing the permanent by importance sampling method.
- Expressing polynomials as the permanent of low rank square matrices
- scientific article; zbMATH DE number 3930346 (Why is no real title available?)
- On the hardness of the noncommutative determinant
- Approximating the permanent via importance sampling with application to the dimer covering problem
- Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
- Singular values of Gaussian matrices and permanent estimators
- Calculation of the permanent of a sparse positive matrix
- A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- An algorithmic proof of Brégman–Minc theorem
- Estimating the permanent by importance sampling from a finite population
- Approximating the permanent of graphs with large factors
- A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)]\) expected speedup for \(0-1\) matrices
- Noncommutativity makes determinants hard
- A permanent formula with many zero-valued terms
- Approximating the number of monomer-dimer coverings of a lattice.
- A permanent formula for the Jones polynomial
- A hybrid algorithm for multi-homogeneous Bézout number
- Clifford algebras and approximating the permanent
- Inverse sampling for nonasymptotic sequential estimation of bounded variable means
- Matching theory -- a sampler: From Dénes König to the present
- Computing the optimal partition of variables in multi-homogeneous homotopy methods
- The permanent of 0-1 matrices and Kallman's algorithm
- On the complexity of computational problems associated with simple stochastic games
- New algorithms for calculation of logarithmic estimates for (0,1)-matrix permanents and their application to problems of chemical kinetics and combinatorial analysis
- A hybrid algorithm for computing permanents of sparse matrices
- An analysis of Monte Carlo algorithm for estimating the permanent
- Non-commutative circuits and the sum-of-squares problem
- A mildly exponential approximation algorithm for the permanent
- scientific article; zbMATH DE number 4082843 (Why is no real title available?)
- A short certificate of the number of universal optimal strategies for stopping simple stochastic games
- Monte Carlo approximation of form factors with error bounded a priori
- An introduction to randomized algorithms
- Random path method with pivoting for computing permanents of matrices
This page was built for publication: A 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 Q4032938)
