A Monte-Carlo Algorithm for Estimating the Permanent
From MaRDI portal
Publication:4032938
DOI10.1137/0222021zbMath0781.05034OpenAlexW1979446688MaRDI QIDQ4032938
Richard J. Lipton, Narendra K. Karmarkar, László Lovász, Michael Luby, Richard M. Karp
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
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Expressing Polynomials as the Permanent of low rank Square Matrices, A permanent formula with many zero-valued terms, A hybrid algorithm for computing permanents of sparse matrices, 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, A hybrid algorithm for multi-homogeneous Bézout number, Singular values of Gaussian matrices and permanent estimators, Random path method with pivoting for computing permanents of matrices, A mildly exponential approximation algorithm for the permanent, Inverse Sampling for Nonasymptotic Sequential Estimation of Bounded Variable Means, Computing the permanent by importance sampling method., On the complexity of computational problems associated with simple stochastic games, Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor, An introduction to randomized algorithms, Matching theory -- a sampler: From Dénes König to the present, Approximating the permanent of graphs with large factors, Calculation of the permanent of a sparse positive matrix, A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes, Computing the optimal partition of variables in multi-homogeneous homotopy methods, Estimating the permanent by importance sampling from a finite population, A permanent formula for the Jones polynomial, On the hardness of the noncommutative determinant, Clifford algebras and approximating the permanent, Non-commutative circuits and the sum-of-squares problem, Approximating the permanent via importance sampling with application to the dimer covering problem, An analysis of Monte Carlo algorithm for estimating the permanent, An algorithmic proof of Brégman–Minc theorem, Approximating the number of monomer-dimer coverings of a lattice., Noncommutativity makes determinants hard
