A Monte-Carlo Algorithm for Estimating the Permanent
DOI10.1137/0222021zbMATH Open0781.05034OpenAlexW1979446688MaRDI QIDQ4032938FDOQ4032938
Authors: Narendra K. Karmarkar, Richard J. Lipton, Michael Luby, Richard Karp, László Lovász 
Publication date: 17 May 1993
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/33c73d6c0e67d57031d4664ad07ece013e4d2855
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
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)
Cited In (35)
- Computing the permanent by importance sampling method.
- Expressing polynomials as the permanent of low rank square matrices
- On the hardness of the noncommutative determinant
- Title not available (Why is that?)
- 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
- An algorithmic proof of Brégman–Minc theorem
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- Calculation of the permanent of a sparse positive matrix
- A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes
- Estimating the permanent by importance sampling from a finite population
- A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)]\) expected speedup for \(0-1\) matrices
- Approximating the permanent of graphs with large factors
- 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
- On the complexity of computational problems associated with simple stochastic games
- Computing the optimal partition of variables in multi-homogeneous homotopy methods
- The permanent of 0-1 matrices and Kallman's algorithm
- 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
- Title not available (Why is that?)
- 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)
